2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 2534 Solved: 1129 [][][]Description
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
4
Sample Output
4
HINT
hint 对于例子(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
Source
题目链接：
id=2818
题目分析：两种姿势，莫比乌斯反演或者欧拉函数，先说简单的方法。欧拉函数，由于仅仅有一个上界n，所以变换一下1 <= x / p, y / p <= n / p，GCD(x / p, y / p) == 1，
直接求欧拉函数，令num[i]表示1到i中 1<=x，y<=i 且gcd(x,y) == 1个对数，显然有num[i] = 1 + phi[j] * 2，(1 < j <= i)，这个1指的是(1, 1)。乘2是由于(1, 2) (2, 1)算两个不同的，那么最后依据我们先前变换的公式。累加num[n / p]的值就可以
#include#include #define ll long longint const MAX = 1e7 + 5;int p[MAX], phi[MAX];bool prime[MAX];ll num[MAX];int pnum;void get_eular(int n){ pnum = 0; memset(prime, true, sizeof(prime)); for(int i = 2; i <= n; i++) { if(prime[i]) { p[pnum ++] = i; phi[i] = i - 1; } for(int j = 0; j < pnum && i * p[j] <= n; j++) { prime[i * p[j]] = false; if(i % p[j] == 0) { phi[i * p[j]] = phi[i] * p[j]; break; } phi[i * p[j]] = phi[i] * (p[j] - 1); } }}int main(){ int n; ll ans = 0; scanf("%d", &n); get_eular(n); num[1] = 1; for(int i = 2; i <= n; i++) num[i] = num[i - 1] + 2 * phi[i]; for(int i = 0; i < pnum; i++) if(n / p[i] > 0) ans += num[n / p[i]]; printf("%lld\n", ans);}
这题也能够用莫比乌斯反演做。还是做上述变换。1 <= x / p, y / p <= n / p，GCD(x / p, y / p) == 1，这样的题真的做烂了，懒得说了直接贴
#include#include #include #define ll long longusing namespace std;int const MAX = 1e7 + 5;int mob[MAX], p[MAX], sum[MAX];bool prime[MAX];int pnum;void Mobius(int n){ pnum = 0; memset(prime, true, sizeof(prime)); memset(sum, 0, sizeof(sum)); mob[1] = 1; sum[1] = 1; for(int i = 2; i <= n; i++) { if(prime[i]) { p[pnum ++] = i; mob[i] = -1; } for(int j = 0; j < pnum && i * p[j] <= n; j++) { prime[i * p[j]] = false; if(i % p[j] == 0) { mob[i * p[j]] = 0; break; } mob[i * p[j]] = -mob[i]; } sum[i] = sum[i - 1] + mob[i]; }}ll cal(int n){ ll res = 0; for(int i = 1, last = 0; i <= n; i = last + 1) { last = n / (n / i); res += (ll) (n / i) * (n / i) * (sum[last] - sum[i - 1]); } return res;}int main(){ int n; ll ans = 0; scanf("%d", &n); Mobius(n); for(int i = 0; i < pnum; i++) if(n / p[i] > 0) ans += cal(n / p[i]); printf("%lld\n", ans);}