HDU-5382 GCD?LCM!


图片说明






图片说明
图片说明

#include<bits/stdc++.h>
#define sc scanf
using namespace std;
const int N=1e6+77;
const int mod=258280327;
typedef long long ll;
int prime[N],mu[N],tot=0;
bool vis[N];
ll A[N],B[N],C[N],D[N];
void f_mod(ll &x){
    if(x>=mod)x-=x/mod*mod;
    if(x<0)x=(x%mod+mod)%mod;
}
int main(){
    mu[1]=1;A[1]=1;
    for(int i=2;i<N;i++){
        A[i]=1;
        if(!vis[i])prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }else mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=tot;i++){
        for(int j=prime[i];j<N;j+=prime[i]){
            int n=j,cnt=0;
            while(n%prime[i]==0)n/=prime[i],cnt++;
            A[j]*=1+cnt;
            f_mod(A[j]);
        }
    }
    for(int i=1;i*i<N;i++){
        for(int j=i*i;j<N;j+=i*i){
            ll x=mu[i]*A[j/i/i];
            f_mod(x);B[j]+=x;f_mod(B[j]);
        }
    }
    for(int i=1;i<N;i++){
        for(int j=i;j<N;j+=i){
            C[j]+=B[j/i-1];
            f_mod(C[j]);
        }
        C[i]+=C[i-1];
        f_mod(C[i]);
    }
    for(int i=1;i<N;i++)D[i]=D[i-1]+1LL*i*i%mod-C[i-1],f_mod(D[i]);
    int t;cin>>t;while(t--){int n;sc("%d",&n);printf("%lld\n",D[n]);}
}