2401: 陶陶的难题I
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 89 Solved: 24
[Submit][Status]
Description
最近陶陶在研究数论，某天他偶然遇到一道题：对于给定的正整数���，求出
下面这样一个式子的值：
其中LCM(a���, b���)表示正整数���和���最小公倍数，即能同时被a���和b���整除的最小正
整数。
作为神犇的陶陶，当然轻松秒杀了这道题。不过他希望你写一个程序，用来
检验他算的答案是否正确。
Input
第一行包含一个正整数���T，表示有T���组测试数据。接下来���T<=10^5
行，每行给出一个正整数N,N<=10^6。
Output
包含T���行，依次给出对应的答案。
Sample Input
7
1
10
100
1000
10000
100000
1000000
1
10
100
1000
10000
100000
1000000
Sample Output
1
2127
18446224
183011304660
1827127167830060
18269345553999897648
182690854273058293758232
最开始试图通过一种很逗逼的做法弄这道题，其实也A的程序复杂度完全相同，都是一个调和计数的O(nlogn)，但是由于我最开始的方法for语句内高精度加要多算那么一两次，所以就稳稳地被卡常数了，而且这个常数致使我删掉了300+的高精度模板，改用一个pair表示int128。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; #define MAXN 1000001 typedef long long qword; int prime[MAXN+10],topp=-1; bool pflag[MAXN+10]; int phi[MAXN+10]; qword maxval=100000000000000000LL; struct mypair { qword first,second; mypair(qword x,qword y):first(x),second(y){}; mypair(){}; inline void operator += (mypair& pp) { first+=pp.first; second+=pp.second; if (second>=maxval) { first++; second-=maxval; } } inline void operator -=(mypair& pp) { first-=pp.first; second-=pp.second; if (second<0) { second+=maxval; first--; } } }; mypair res[MAXN+10]; void init() { register int i,j; phi[1]=1; for (i=2;i<MAXN;i++) { if (!pflag[i]) { prime[++topp]=i; phi[i]=i-1; } for (j=0;j<=topp && i*prime[j]<MAXN;j++) { pflag[i*prime[j]]=true; if (i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } } register mypair g,gt,g0; g.first=g.second=0;; for (i=1;i<MAXN;i++)res[i].first=0,res[i].second=0; for (i=1;i<MAXN;i++) { g.first+=(qword)i*i*phi[i]/maxval; g.second+=(qword)i*i*phi[i]%maxval; if (g.second>=maxval) { g.first+=g.second/maxval; g.second%=maxval; } gt.first=gt.second=0;g0=g; for (j=1;i*j<MAXN;j++) { gt+=g0; res[i*j]+=gt; if (i*j+j<MAXN) { res[(i+1)*j]-=gt; } } } //for (i=1;i<MAXN;i++)res[i].first-=100000; for (i=2;i<MAXN;i++) res[i]+=res[i-1]; } int main() { //freopen("input.txt","r",stdin); //freopen("b.txt","w",stdout); init(); qword i,j,k,x,y,z,n,m; qword nn; scanf("%lld",&nn); qword ans=0; while (nn--) { scanf("%lld",&n); if (res[n].first) printf("%lld%017lld ",res[n].first,res[n].second); else printf("%lld ",res[n].second); } }
换了一种方法，联想lcmsum的做法，通过与n互质数的和为n*phi[n]/2这个公式可以很轻松推出正解，但是还是非常慢，至少还是可以A掉吧。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; #define MAXN 1000001 typedef unsigned long long qword; int prime[MAXN+10],topp=-1; bool pflag[MAXN+10]; int phi[MAXN+10]; qword maxval=100000000000000000LLU; struct mypair { qword first,second; mypair(qword x,qword y):first(x),second(y){}; mypair(){}; inline void operator += (mypair& pp) { first+=pp.first; second+=pp.second; if (second>=maxval) { first++; second-=maxval; } } inline void operator -=(mypair& pp) { first-=pp.first; second-=pp.second; if (second<0) { second+=maxval; first--; } } }; mypair res[MAXN+10]; void init() { register int i,j; phi[1]=1; for (i=2;i<MAXN;i++) { if (!pflag[i]) { prime[++topp]=i; phi[i]=i-1; } for (j=0;j<=topp && i*prime[j]<MAXN;j++) { pflag[i*prime[j]]=true; if (i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } } for (i=1;i<MAXN;i++) { register qword x=(qword)phi[i]*i/2; if (i==1)x=1; for (j=i;j<MAXN;j+=i) { res[j].second+=x*j; if (res[j].second>=maxval) { res[j].first+=res[j].second/maxval; res[j].second%=maxval; } } } for (i=1;i<MAXN;i++) { res[i].first*=2,res[i].second*=2; res[i].second-=i; if (res[i].second>=maxval) { res[i].second-=maxval; res[i].first++; } if (res[i].second<0) { res[i].second+=maxval; res[i].first--; } res[i]+=res[i-1]; } return ; /* register mypair g,gt,g0; g.first=g.second=0;; for (i=1;i<MAXN;i++)res[i].first=0,res[i].second=0; for (i=1;i<MAXN;i++) { g.second+=(qword)i*i*phi[i]; if (g.second>=maxval) { g.first+=g.second/maxval; g.second%=maxval; } gt.first=gt.second=0;g0=g; for (j=1;i*j<MAXN;j++) { gt+=g0; res[i*j]+=gt; if (i*j+j<MAXN) { res[(i+1)*j]-=gt; } } } for (i=2;i<MAXN;i++) res[i]+=res[i-1];*/ } int main() { //freopen("input.txt","r",stdin); //freopen("b.txt","w",stdout); init(); qword i,j,k,x,y,z,n,m; qword nn; scanf("%lld",&nn); qword ans=0; while (nn--) { scanf("%lld",&n); if (res[n].first) printf("%llu%017llu ",res[n].first,res[n].second); else printf("%llu ",res[n].second); } }