hint
对于样例 (2,2),(2,4),(3,3),(4,2)
1<=N<=10^7 题解一(自己 yy)
phi[i] 表示与 x 互质的数的个数
即 gcd(x,y)=1 1<=y<x
∴对于 x,y 若 a 为素数
则 gcd(xa,ya)=a
即满足 xa<=N 即可,这个答案即为满足条件数的个数
n 是 10e7,可以 O(N)先求出 phi
一种方法可以 N log N 即,二分质数使其满足,但不够优秀
发现 x(枚举值)不断增大,即质数个数不断减少,所以单调性
所以 O(N)即可。
题解二
求 1<=x,y<=N 且 Gcd(x,y)为素数的数对 (x,y) 有多少对
枚举每个素数,然后每个素数 p 对于答案的贡献就是(1 ~ n / p) 中有序互质对的个数
而求 1~m 中有序互质对 x,y 的个数,可以令 y >= x, 当 y = x 时,有且只有 y = x = 1 互质,
当 y > x 时,确定 y 以后符合条件的个数 x 就是 phiy
所以有序互质对的个数为(1 ~ n/p)的欧拉函数之和乘 2 减 1(要求的是有序互质对,乘 2 以后减去(1, 1)多算的一次)
那么就只需要先筛出欧拉函数再求个前缀和就可以了
思路二更优秀,hzw 大佬。
- #include < iostream > #include < cstdio > #define ll long long#define N 10000005 using namespace std;
- int n,
- p,
- tot;
- int phi[N],
- pri[1000005];
- bool mark[N];
- ll ans,
- sum[N];
- void getphi() {
- phi[1] = 1;
- for (int i = 2; i <= n; i++) {
- if (!mark[i]) {
- phi[i] = i - 1;
- pri[++tot] = i;
- }
- for (int j = 1; j <= tot; j++) {
- int x = pri[j];
- if (i * x > n) break;
- mark[i * x] = 1;
- if (i % x == 0) {
- phi[i * x] = phi[i] * x;
- break;
- } else phi[i * x] = phi[i] * phi[x];
- }
- }
- }
- int main() {
- scanf("%d", &n);
- getphi();
- for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + phi[i];
- for (int i = 1; i <= tot; i++) ans += sum[n / pri[i]] * 2 - 1;
- printf("%lld", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2438913.html