UVA11424 GCD - Extreme (I) 题解
题目链接:UVA11424 GCD - Extreme (I)
题意:
给定 n ,求
n∑i=1n∑j=i+1gcd(i,j)1<n≤2×105 ,最多 2×104 组数据。
据说是「7倍经验」,那我干脆一并写了吧。
这道题有很多种解法,常见的解法是欧拉函数和莫比乌斯反演。
解法1:欧拉函数
正解解法。记 f(n)=∑ni=1gcd(i,n) ,则答案为 ∑ni=1f(i)
考虑怎么快速计算 f 。设 g(i,n) 为对于所有的 x(1≤x<n) ,gcd(x,n)=i 的 x 的个数,则
f(n)=∑d∣ng(d,n)注意到 gcd(x,n)=i ,意味着 gcd(x/i,n/i)=1 ,也就是 x/i 与 n/i 互质,故
f(n)=∑d∣nφ(n/i)感觉有点对劲,但好像又不是很对劲。直接枚举因数会比较慢,因此我们可以反过来计算贡献。
时间复杂度 O(nlogn)
代码:
cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
bitset<N> ck; int pcnt,phi[N],f[N],sum[N],prime[N];
void Euler(int n = N - 10)
{
phi[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!ck[i]) { prime[++pcnt] = i; phi[i] = i - 1; }
for(int j = 1; j <= pcnt && i * prime[j] <= n; j++)
{
int pos = i * prime[j]; ck[pos] = true;
if(i % prime[j]) {
phi[pos] = phi[i] * phi[prime[j]];
} else { phi[pos] = phi[i] * prime[j]; break; }
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
Euler();
for(int i = 1; i <= N - 10; i++)
for(int j = i * 2; j <= N - 10; j += i) f[j] += i * phi[j / i];
sum[2] = f[2];
for(int i = 3; i <= N - 10; i++) sum[i] = sum[i - 1] + f[i];
for(int n; cin >> n && n != 0; ) cout << sum[n] << '\n';
return 0;
}
解法2:莫比乌斯反演
这个也是我自己想到的解法(不是正解),不过在这道题就需要卡一卡常。
我们先来推推式子:(这个式子的结果 x 与原答案 x0 的关系为 x=2x0+n(n+1)2 )
n∑i=1n∑j=1gcd(i,j)=n∑k=1kn∑i=1n∑j=1[gcd(i,j)=k]=n∑k=1kn/k∑i=1n/k∑j=1[gcd(i,j)=1]=n∑k=1kn/k∑i=1n/k∑j=1∑d∣gcd(i,j)μ(d)=n∑k=1kn/k∑d=1μ(d)n/k∑i=1[d∣i]n/k∑j=1[d∣j]=n∑k=1kn/k∑d=1μ(d)⌊nkd⌋2然而直接搞是过不了的,因为数据组数太多:
O(√n1+√n2+⋯+√nn)=O(√n(1+1√2+⋯+1√n))=O(n)考虑设 m=n/k ,则
n∑k=1km∑d=1μ(d)⌊md⌋2后面的部分在 m 固定时与 k 无关,考虑预处理为 f(m) ,则
n∑k=1k⋅f(n/k)时间复杂度 O(N√N) ,但是需要卡常,原理参考link。
代码:(用时 1.17s )
cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename A, typename ...B>
void read(A &x, B &...y) { return read(x), read(y...); }
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N ((int)(2e5 + 15))
bitset<N> ck; int pcnt,mu[N],f[N],v[N],prime[N];
void Mobius(int n = N - 10)
{
mu[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!ck[i]) { prime[++pcnt] = i; mu[i] = -1; }
for(int j = 1; j <= pcnt && i * prime[j] <= n; j++)
{
int pos = i * prime[j]; ck[pos] = true;
if(i % prime[j]) { mu[pos] = -mu[i]; } else { mu[pos] = 0; break; }
}
}
for(int i = 1; i <= n; i++) mu[i] += mu[i - 1];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
Mobius();
for(int i = 1; i <= N - 10; i++)
{
int sq = sqrt(i), cnt = 2 * sq;
for(int j = 1; j <= sq; j++) { v[j] = j; v[cnt - j + 1] = i / j; }
for(int k = 1, j = cnt; k <= cnt; k++,j--) f[i] += v[k] * v[k] * (mu[v[j]] - mu[v[j - 1]]);
}
for(int n; read(n), n != 0; )
{
int res = 0;
for(int l = 1, r; l <= n; l = r + 1)
{
r = n / (n / l);
res += (f[n / l] - 1) * (l + r) * (r - l + 1) / 2;
}
write(res / 2); pc('\n');
}
return 0;
}
其他题
- UVA11426 拿行李(极限版) GCD - Extreme (II) 只需要把 N 改一下就能过了。
- 洛谷P1390 公约数的和 删掉多组询问,然后把 N 改一下就能过了。
- 洛谷P2398 GCD SUM 删掉多组询问,把 N 改一下,把输出改一下就能过了。
- 洛谷P2568 GCD 写过题解,看这边 link
- SP3871 GCDEX - GCD Extreme 只需要把 N 改一下就能过了(搬题小能手SPOJ)
- UVA11417 GCD 本题简化版,直接交
- 算上本题,正好7倍经验,蛮好的。