首页 > 代码库 > BZOJ[SPOJ5971]LCMSum
BZOJ[SPOJ5971]LCMSum
Description
Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each test case, containing the required sum.
Sample Input
3
1
2
5
1
2
5
Sample Output
1
4
55
4
55
HINT
1 <= T <= 300000
1 <= n <= 1000000
题解：
题意即求∑LCM(i,n)（1<=i<=n）。
枚举lcm，统计对答案的贡献。
原本我采用的方法是容斥，求出n的因数表后，由大到小枚举lcm[i]，并把更小的lcm[j]的贡献减去相应的值。
复杂度还可以，但是常数非常大，在BZ上过不了。
有一个常数更小的方法：枚举lcm后，我们需要知道1~n div lcm-1中所有与n div lcm互质的数的和。
设m=n div lcm。若x与m互质，则m-x与m互质，即与m互质的数成对出现，所以与m互质的数的和为m*φ(m)div 2。（m<=2时依旧成立）
线性筛预处理出欧拉函数，就可以快速求值了。
代码：
TLE的容斥（P++注意）：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define begin { 4 #define end } 5 #define while while( 6 #define if if( 7 #define do ) 8 #define then ) 9 #define for for( 10 #define fillchar(a,b,c) memset(a,c,b) 11 #define writeln printf("\n") 12 #define write printf 13 #define readln readl() 14 #define inc(a) a++ 15 #define dec(a) a-- 16 #define exit(a) return a 17 #define mod % 18 #define div / 19 #define shl << 20 #define shr >> 21 #define extended long double 22 #define longint int 23 #define integer short 24 #define int64 long long 25 template<typename T> inline void read(T& a) 26 begin 27 T x=0,f=1; char ch=getchar(); 28 while(ch<‘0‘)or(ch>‘9‘)do 29 begin 30 if ch==‘-‘ then f=-1; ch=getchar(); 31 end 32 while(ch>=‘0‘)and(ch<=‘9‘)do 33 begin 34 x=x*10+ch-‘0‘; ch=getchar(); 35 end 36 a=x*f; 37 end 38 inline void readl() 39 begin 40 char ch; ch=getchar(); 41 while ch!=‘\n‘ do ch=getchar(); 42 end 43 int64 i,t,ii,j,n,m,x,a[3002],b[1000002],ans; 44 int main() 45 begin 46 read(t); 47 for ii=1;ii<=t;ii++ do 48 begin 49 read(x); j=sqrt(x); n=0; m=0; ans=0; 50 for i=1;i<=j;i++ do 51 begin 52 if x mod i==0 then 53 begin 54 inc(n); a[n]=i; 55 if x div i>i then begin inc(m); a[2002-m]=x div i; end; 56 end 57 end 58 for i=n+1;i<=n+m;i++ do a[i]=a[2002-(m-(i-n)+1)]; 59 n=n+m; 60 for i=1;i<=n;i++ do b[a[i]]=0; 61 for i=n;i>=1;i-- do 62 begin 63 b[a[i]]=b[a[i]]+(1+x div a[i])*(x div a[i])div 2; 64 ans=ans+b[a[i]]*x; 65 j=1; 66 while a[j]*a[j]<=a[i] do 67 begin 68 if j>n then break; 69 if a[i] mod a[j]==0 then 70 begin 71 b[a[j]]=b[a[j]]-(a[i] div a[j])*b[a[i]]; 72 if(a[j]*a[j]<a[i])and(a[j]>1)then 73 b[a[i] div a[j]]=b[a[i] div a[j]]-a[j]*b[a[i]]; 74 end 75 inc(j); 76 end 77 end 78 write("%lld",ans); writeln; 79 end 80 end
标程（P++注意）：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define begin { 4 #define end } 5 #define while while( 6 #define if if( 7 #define do ) 8 #define then ) 9 #define for for( 10 #define fillchar(a,b,c) memset(a,c,b) 11 #define writeln printf("\n") 12 #define write printf 13 #define readln readl() 14 #define inc(a) a++ 15 #define dec(a) a-- 16 #define exit(a) return a 17 #define mod % 18 #define div / 19 #define shl << 20 #define shr >> 21 #define extended long double 22 #define longint int 23 #define integer short 24 #define int64 long long 25 template<typename T> inline void read(T& a) 26 begin 27 T x=0,f=1; char ch=getchar(); 28 while(ch<‘0‘)or(ch>‘9‘)do 29 begin 30 if ch==‘-‘ then f=-1; ch=getchar(); 31 end 32 while(ch>=‘0‘)and(ch<=‘9‘)do 33 begin 34 x=x*10+ch-‘0‘; ch=getchar(); 35 end 36 a=x*f; 37 end 38 inline void readl() 39 begin 40 char ch; ch=getchar(); 41 while ch!=‘\n‘ do ch=getchar(); 42 end 43 longint p[1000100],vis[1000100],ph[1000100],pcnt=0,T,n; 44 void init_p() 45 begin 46 ph[1]=1; ph[2]=1; 47 int64 temp; 48 for int i=2;i<1000100;i++ do 49 begin 50 if not vis[i] then 51 begin 52 p[pcnt]=i; ph[i]=i-1; inc(pcnt); 53 end 54 for int j=0;j<pcnt&&(temp=(int64)p[j]*i)<1000100;j++ do 55 begin 56 vis[temp]=1; 57 if i mod p[j]==0 then begin ph[temp]=ph[i]*p[j]; break; end 58 else ph[temp]=ph[i]*(p[j]-1); 59 end 60 end 61 end 62 int64 solve(int n) 63 begin 64 int64 ans=0ll; 65 longint half=(int)(sqrt(n)+0.01); 66 if half*half==n then begin ans+=1ll*ph[half]*half/2; dec(half); end 67 inc(ans); ans+=1ll*ph[n]*n/2; 68 for int i=2;i<=half;i++ do 69 if n mod i==0 then 70 begin 71 ans+=1ll*ph[i]*i/2; 72 ans+=1ll*ph[n/i]*n/i/2; 73 end 74 exit(ans*n); 75 } 76 int main() 77 begin 78 read(T); init_p(); 79 for int i=1;i<=T;i++ do 80 begin read(n); write("%lld",solve(n)); writeln; end 81 return 0; 82 end
BZOJ[SPOJ5971]LCMSum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。