Gcd
[Time Limit: 10000 msquad Memory Limit: 262144 kB
]
题意
求 (gcdleft(x，y ight) = p) 的对数，其中(1 leq x,y leq n)且 (p)是质数
思路
(gleft(x
ight)) 表示 (gcdleft(a, b
ight) | x) 的对数
(fleft(x
ight)) 表示 (gcdleft(a, b
ight) = x) 的对数
根据莫比乌斯反演有
[ fleft(n
ight) = sum_{n|d} gleft(d
ight)\
gleft(n
ight) = sum_{n|d} muleft(frac{d}{n}
ight) fleft(d
ight) \
]
根据题意
[ fleft(x
ight) = lfloorfrac{n}{x}
floor lfloorfrac{n}{x}
floor \
]
那么就可以得到
[egin{aligned}
ans &= sum_{prime(p)} gleft(p
ight) \
&= sum_{prime(p)} sum_{p|d} muleft(frac{d}{p}
ight) lfloorfrac{n}{d}
floor lfloorfrac{n}{d}
floor \
end{aligned}
]
对于每个 (d)，找到所有满足 (p|d) 的 (prime(p))，预处理出 (sum_{p|d}muleft(frac{d}{p} ight))。
- 如果 (d) 是质数，容易得到 (sum[d] = 1)。
- 如果 (d) 不是质数，那么可以把 (d) 看成 (p_{1}^{a1}p_{2}^{a2}...p_{k}^{ak})，设 (d = p_{1}x)
[egin{aligned}
sum_{p|d} muleft(frac{d}{p}
ight) &= muleft(frac{d}{p_{1}}
ight)+muleft(frac{d}{p_{2}}
ight)+...+muleft(frac{d}{p_{k}}
ight)\
&= muleft(x
ight) + muleft(frac{p_{1}x}{p_{2}}
ight)+...+muleft(frac{p_{1}x}{p_{k}}
ight) \
sum_{p|x}muleft(frac{x}{p}
ight) &= muleft(frac{x}{p_{2}}
ight)+...+muleft(frac{x}{p_{k}}
ight)
end{aligned}
]
因为(p_{k}|d，d=p_{1}x)，则 (p_{k}|x)。那么现在的问题就在于 (p_{1}|x)。
(quad) 1. 若 (p1|x)，则对于 (left(frac{p_{1}x}{p_{k}}
ight))，可以发现除完以后，仍然会包括两个及以上 (p_{1}) 因子，所以其 (mu) 值为(0)。
(quad) 2. 反之，(left(frac{p_{1}x}{p_{k}}
ight)) 在 (left(frac{x}{p_{k}}
ight))的基础上多了一个 (p_{1}) 因子且指数为 (1)，根据 (mu) 的公式，(muleft(frac{p_{1}x}{p_{k}}
ight) =- muleft(frac{x}{p_{k}}
ight))。
综合上述
[sum_{p|d} muleft(frac{d}{p}
ight) =
egin{cases}
muleft(x
ight) & p_{1}|x\
muleft(x
ight) - sum_{x|d} muleft(frac{x}{p}
ight) &otherwise\
end{cases}
]
/***************************************************************
> File Name : a.cpp
> Author : Jiaaaaaaaqi
> Created Time : 2019年07月17日 星期三 10时20分16秒
***************************************************************/
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pii pair<int, int>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e7 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
ll n, m;
int cas, tol, T;
int pri[maxn], mob[maxn];
bool ispri[maxn];
ll sum[maxn];
void handle() {
mes(sum, 0), mes(pri, 0), mes(ispri, 1);
tol = 0;
mob[1] = 1;
int mx = 1e7;
for(int i=2; i<=mx; i++) {
if(ispri[i]) {
pri[++tol] = i;
mob[i] = -1;
sum[i] = 1;
}
for(int j=1; j<=tol && i*pri[j]<=mx; j++) {
ispri[i*pri[j]] = false;
if(i%pri[j] == 0) {
mob[i*pri[j]] = 0;
sum[i*pri[j]] = mob[i];
break;
} else {
mob[i*pri[j]] = -mob[i];
sum[i*pri[j]] = mob[i] - sum[i];
}
}
}
}
int main() {
handle();
printf("%lld %lld %lld
", sum[12], sum[6], mob[6]);
scanf("%lld", &n);
ll ans = 0;
for(ll d=2; d<=n; d++) {
ans += 1ll*sum[d]*(n/d)*(n/d);
}
printf("%lld
", ans);
return 0;
}