正文
BZOJ2226:[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
Sample Output
1
4
55
HINT
1 <= T <= 300000
1 <= n <= 1000000
题解：
题意即求∑LCM(i,n)（1<=i<=n）。
枚举gcd，统计对答案的贡献。
原本我采用的方法是容斥，求出n的因数表后，由大到小枚举gcd[i]，并把更小的gcd[j]的贡献减去相应的值。
复杂度还可以，但是常数非常大，在BZ上过不了。
有一个常数更小的方法：枚举gcd后，我们需要知道1~n div gcd-1中所有与n div gcd互质的数的和。
设m=n div gcd。若x与m互质，则m-x与m互质，即与m互质的数成对出现，所以与m互质的数的和为m*φ(m)div 2。（m<=2时依旧成立）
线性筛预处理出欧拉函数，就可以快速求值了。
代码：
TLE的容斥（P++注意）：
#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("\n")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
T x=,f=; char ch=getchar();
while(ch<'')or(ch>'')do
begin
if ch=='-' then f=-; ch=getchar();
end
while(ch>='')and(ch<='')do
begin
x=x*+ch-''; ch=getchar();
end
a=x*f;
end
inline void readl()
begin
char ch; ch=getchar();
while ch!='\n' do ch=getchar();
end
int64 i,t,ii,j,n,m,x,a[],b[],ans;
int main()
begin
read(t);
for ii=;ii<=t;ii++ do
begin
read(x); j=sqrt(x); n=; m=; ans=;
for i=;i<=j;i++ do
begin
if x mod i== then
begin
inc(n); a[n]=i;
if x div i>i then begin inc(m); a[-m]=x div i; end;
end
end
for i=n+;i<=n+m;i++ do a[i]=a[-(m-(i-n)+)];
n=n+m;
for i=;i<=n;i++ do b[a[i]]=;
for i=n;i>=;i-- do
begin
b[a[i]]=b[a[i]]+(+x div a[i])*(x div a[i])div ;
ans=ans+b[a[i]]*x;
j=;
while a[j]*a[j]<=a[i] do
begin
if j>n then break;
if a[i] mod a[j]== then
begin
b[a[j]]=b[a[j]]-(a[i] div a[j])*b[a[i]];
if(a[j]*a[j]<a[i])and(a[j]>)then
b[a[i] div a[j]]=b[a[i] div a[j]]-a[j]*b[a[i]];
end
inc(j);
end
end
write("%lld",ans); writeln;
end
end
标程（P++注意）：
#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("\n")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
T x=,f=; char ch=getchar();
while(ch<'')or(ch>'')do
begin
if ch=='-' then f=-; ch=getchar();
end
while(ch>='')and(ch<='')do
begin
x=x*+ch-''; ch=getchar();
end
a=x*f;
end
inline void readl()
begin
char ch; ch=getchar();
while ch!='\n' do ch=getchar();
end
longint p[],vis[],ph[],pcnt=,T,n;
void init_p()
begin
ph[]=; ph[]=;
int64 temp;
for int i=;i<;i++ do
begin
if not vis[i] then
begin
p[pcnt]=i; ph[i]=i-; inc(pcnt);
end
for int j=;j<pcnt&&(temp=(int64)p[j]*i)<;j++ do
begin
vis[temp]=;
if i mod p[j]== then begin ph[temp]=ph[i]*p[j]; break; end
else ph[temp]=ph[i]*(p[j]-);
end
end
end
int64 solve(int n)
begin
int64 ans=0ll;
longint half=(int)(sqrt(n)+0.01);
if half*half==n then begin ans+=1ll*ph[half]*half/; dec(half); end
inc(ans); ans+=1ll*ph[n]*n/;
for int i=;i<=half;i++ do
if n mod i== then
begin
ans+=1ll*ph[i]*i/;
ans+=1ll*ph[n/i]*n/i/;
end
exit(ans*n);
}
int main()
begin
read(T); init_p();
for int i=;i<=T;i++ do
begin read(n); write("%lld",solve(n)); writeln; end
return ;
end
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
Sample Output
1
4
55
HINT
1 <= T <= 300000
1 <= n <= 1000000
题解：
题意即求∑LCM(i,n)（1<=i<=n）。
枚举gcd，统计对答案的贡献。
原本我采用的方法是容斥，求出n的因数表后，由大到小枚举gcd[i]，并把更小的gcd[j]的贡献减去相应的值。
复杂度还可以，但是常数非常大，在BZ上过不了。
有一个常数更小的方法：枚举gcd后，我们需要知道1~n div gcd-1中所有与n div gcd互质的数的和。
设m=n div gcd。若x与m互质，则m-x与m互质，即与m互质的数成对出现，所以与m互质的数的和为m*φ(m)div 2。（m<=2时依旧成立）
线性筛预处理出欧拉函数，就可以快速求值了。
代码：
TLE的容斥（P++注意）：
#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("\n")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
T x=,f=; char ch=getchar();
while(ch<'')or(ch>'')do
begin
if ch=='-' then f=-; ch=getchar();
end
while(ch>='')and(ch<='')do
begin
x=x*+ch-''; ch=getchar();
end
a=x*f;
end
inline void readl()
begin
char ch; ch=getchar();
while ch!='\n' do ch=getchar();
end
int64 i,t,ii,j,n,m,x,a[],b[],ans;
int main()
begin
read(t);
for ii=;ii<=t;ii++ do
begin
read(x); j=sqrt(x); n=; m=; ans=;
for i=;i<=j;i++ do
begin
if x mod i== then
begin
inc(n); a[n]=i;
if x div i>i then begin inc(m); a[-m]=x div i; end;
end
end
for i=n+;i<=n+m;i++ do a[i]=a[-(m-(i-n)+)];
n=n+m;
for i=;i<=n;i++ do b[a[i]]=;
for i=n;i>=;i-- do
begin
b[a[i]]=b[a[i]]+(+x div a[i])*(x div a[i])div ;
ans=ans+b[a[i]]*x;
j=;
while a[j]*a[j]<=a[i] do
begin
if j>n then break;
if a[i] mod a[j]== then
begin
b[a[j]]=b[a[j]]-(a[i] div a[j])*b[a[i]];
if(a[j]*a[j]<a[i])and(a[j]>)then
b[a[i] div a[j]]=b[a[i] div a[j]]-a[j]*b[a[i]];
end
inc(j);
end
end
write("%lld",ans); writeln;
end
end
标程（P++注意）：
#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("\n")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
T x=,f=; char ch=getchar();
while(ch<'')or(ch>'')do
begin
if ch=='-' then f=-; ch=getchar();
end
while(ch>='')and(ch<='')do
begin
x=x*+ch-''; ch=getchar();
end
a=x*f;
end
inline void readl()
begin
char ch; ch=getchar();
while ch!='\n' do ch=getchar();
end
longint p[],vis[],ph[],pcnt=,T,n;
void init_p()
begin
ph[]=; ph[]=;
int64 temp;
for int i=;i<;i++ do
begin
if not vis[i] then
begin
p[pcnt]=i; ph[i]=i-; inc(pcnt);
end
for int j=;j<pcnt&&(temp=(int64)p[j]*i)<;j++ do
begin
vis[temp]=;
if i mod p[j]== then begin ph[temp]=ph[i]*p[j]; break; end
else ph[temp]=ph[i]*(p[j]-);
end
end
end
int64 solve(int n)
begin
int64 ans=0ll;
longint half=(int)(sqrt(n)+0.01);
if half*half==n then begin ans+=1ll*ph[half]*half/; dec(half); end
inc(ans); ans+=1ll*ph[n]*n/;
for int i=;i<=half;i++ do
if n mod i== then
begin
ans+=1ll*ph[i]*i/;
ans+=1ll*ph[n/i]*n/i/;
end
exit(ans*n);
}
int main()
begin
read(T); init_p();
for int i=;i<=T;i++ do
begin read(n); write("%lld",solve(n)); writeln; end
return ;
end
3
1
2
5
1
2
5
Sample Output
1
4
55
HINT
1 <= T <= 300000
1 <= n <= 1000000
题解：
题意即求∑LCM(i,n)（1<=i<=n）。
枚举gcd，统计对答案的贡献。
原本我采用的方法是容斥，求出n的因数表后，由大到小枚举gcd[i]，并把更小的gcd[j]的贡献减去相应的值。
复杂度还可以，但是常数非常大，在BZ上过不了。
有一个常数更小的方法：枚举gcd后，我们需要知道1~n div gcd-1中所有与n div gcd互质的数的和。
设m=n div gcd。若x与m互质，则m-x与m互质，即与m互质的数成对出现，所以与m互质的数的和为m*φ(m)div 2。（m<=2时依旧成立）
线性筛预处理出欧拉函数，就可以快速求值了。
代码：
TLE的容斥（P++注意）：
#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("\n")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
T x=,f=; char ch=getchar();
while(ch<'')or(ch>'')do
begin
if ch=='-' then f=-; ch=getchar();
end
while(ch>='')and(ch<='')do
begin
x=x*+ch-''; ch=getchar();
end
a=x*f;
end
inline void readl()
begin
char ch; ch=getchar();
while ch!='\n' do ch=getchar();
end
int64 i,t,ii,j,n,m,x,a[],b[],ans;
int main()
begin
read(t);
for ii=;ii<=t;ii++ do
begin
read(x); j=sqrt(x); n=; m=; ans=;
for i=;i<=j;i++ do
begin
if x mod i== then
begin
inc(n); a[n]=i;
if x div i>i then begin inc(m); a[-m]=x div i; end;
end
end
for i=n+;i<=n+m;i++ do a[i]=a[-(m-(i-n)+)];
n=n+m;
for i=;i<=n;i++ do b[a[i]]=;
for i=n;i>=;i-- do
begin
b[a[i]]=b[a[i]]+(+x div a[i])*(x div a[i])div ;
ans=ans+b[a[i]]*x;
j=;
while a[j]*a[j]<=a[i] do
begin
if j>n then break;
if a[i] mod a[j]== then
begin
b[a[j]]=b[a[j]]-(a[i] div a[j])*b[a[i]];
if(a[j]*a[j]<a[i])and(a[j]>)then
b[a[i] div a[j]]=b[a[i] div a[j]]-a[j]*b[a[i]];
end
inc(j);
end
end
write("%lld",ans); writeln;
end
end
标程（P++注意）：
#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("\n")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
T x=,f=; char ch=getchar();
while(ch<'')or(ch>'')do
begin
if ch=='-' then f=-; ch=getchar();
end
while(ch>='')and(ch<='')do
begin
x=x*+ch-''; ch=getchar();
end
a=x*f;
end
inline void readl()
begin
char ch; ch=getchar();
while ch!='\n' do ch=getchar();
end
longint p[],vis[],ph[],pcnt=,T,n;
void init_p()
begin
ph[]=; ph[]=;
int64 temp;
for int i=;i<;i++ do
begin
if not vis[i] then
begin
p[pcnt]=i; ph[i]=i-; inc(pcnt);
end
for int j=;j<pcnt&&(temp=(int64)p[j]*i)<;j++ do
begin
vis[temp]=;
if i mod p[j]== then begin ph[temp]=ph[i]*p[j]; break; end
else ph[temp]=ph[i]*(p[j]-);
end
end
end
int64 solve(int n)
begin
int64 ans=0ll;
longint half=(int)(sqrt(n)+0.01);
if half*half==n then begin ans+=1ll*ph[half]*half/; dec(half); end
inc(ans); ans+=1ll*ph[n]*n/;
for int i=;i<=half;i++ do
if n mod i== then
begin
ans+=1ll*ph[i]*i/;
ans+=1ll*ph[n/i]*n/i/;
end
exit(ans*n);
}
int main()
begin
read(T); init_p();
for int i=;i<=T;i++ do
begin read(n); write("%lld",solve(n)); writeln; end
return ;
end
4
55
1 <= T <= 300000
1 <= n <= 1000000
题解：
题意即求∑LCM(i,n)（1<=i<=n）。
枚举gcd，统计对答案的贡献。
原本我采用的方法是容斥，求出n的因数表后，由大到小枚举gcd[i]，并把更小的gcd[j]的贡献减去相应的值。
复杂度还可以，但是常数非常大，在BZ上过不了。
有一个常数更小的方法：枚举gcd后，我们需要知道1~n div gcd-1中所有与n div gcd互质的数的和。
设m=n div gcd。若x与m互质，则m-x与m互质，即与m互质的数成对出现，所以与m互质的数的和为m*φ(m)div 2。（m<=2时依旧成立）
线性筛预处理出欧拉函数，就可以快速求值了。
代码：
TLE的容斥（P++注意）：
#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("\n")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
T x=,f=; char ch=getchar();
while(ch<'')or(ch>'')do
begin
if ch=='-' then f=-; ch=getchar();
end
while(ch>='')and(ch<='')do
begin
x=x*+ch-''; ch=getchar();
end
a=x*f;
end
inline void readl()
begin
char ch; ch=getchar();
while ch!='\n' do ch=getchar();
end
int64 i,t,ii,j,n,m,x,a[],b[],ans;
int main()
begin
read(t);
for ii=;ii<=t;ii++ do
begin
read(x); j=sqrt(x); n=; m=; ans=;
for i=;i<=j;i++ do
begin
if x mod i== then
begin
inc(n); a[n]=i;
if x div i>i then begin inc(m); a[-m]=x div i; end;
end
end
for i=n+;i<=n+m;i++ do a[i]=a[-(m-(i-n)+)];
n=n+m;
for i=;i<=n;i++ do b[a[i]]=;
for i=n;i>=;i-- do
begin
b[a[i]]=b[a[i]]+(+x div a[i])*(x div a[i])div ;
ans=ans+b[a[i]]*x;
j=;
while a[j]*a[j]<=a[i] do
begin
if j>n then break;
if a[i] mod a[j]== then
begin
b[a[j]]=b[a[j]]-(a[i] div a[j])*b[a[i]];
if(a[j]*a[j]<a[i])and(a[j]>)then
b[a[i] div a[j]]=b[a[i] div a[j]]-a[j]*b[a[i]];
end
inc(j);
end
end
write("%lld",ans); writeln;
end
end
标程（P++注意）：
#include <bits/stdc++.h>
using namespace std;
#define begin {
#define end }
#define while while(
#define if if(
#define do )
#define then )
#define for for(
#define fillchar(a,b,c) memset(a,c,b)
#define writeln printf("\n")
#define write printf
#define readln readl()
#define inc(a) a++
#define dec(a) a--
#define exit(a) return a
#define mod %
#define div /
#define shl <<
#define shr >>
#define extended long double
#define longint int
#define integer short
#define int64 long long
template<typename T> inline void read(T& a)
begin
T x=,f=; char ch=getchar();
while(ch<'')or(ch>'')do
begin
if ch=='-' then f=-; ch=getchar();
end
while(ch>='')and(ch<='')do
begin
x=x*+ch-''; ch=getchar();
end
a=x*f;
end
inline void readl()
begin
char ch; ch=getchar();
while ch!='\n' do ch=getchar();
end
longint p[],vis[],ph[],pcnt=,T,n;
void init_p()
begin
ph[]=; ph[]=;
int64 temp;
for int i=;i<;i++ do
begin
if not vis[i] then
begin
p[pcnt]=i; ph[i]=i-; inc(pcnt);
end
for int j=;j<pcnt&&(temp=(int64)p[j]*i)<;j++ do
begin
vis[temp]=;
if i mod p[j]== then begin ph[temp]=ph[i]*p[j]; break; end
else ph[temp]=ph[i]*(p[j]-);
end
end
end
int64 solve(int n)
begin
int64 ans=0ll;
longint half=(int)(sqrt(n)+0.01);
if half*half==n then begin ans+=1ll*ph[half]*half/; dec(half); end
inc(ans); ans+=1ll*ph[n]*n/;
for int i=;i<=half;i++ do
if n mod i== then
begin
ans+=1ll*ph[i]*i/;
ans+=1ll*ph[n/i]*n/i/;
end
exit(ans*n);
}
int main()
begin
read(T); init_p();
for int i=;i<=T;i++ do
begin read(n); write("%lld",solve(n)); writeln; end
return ;
end
