本文共 2525 字，大约阅读时间需要 8 分钟。

题目

同标题

题目描述
输入$N$和$M(2\le N\le 1000000000,1\le M\le N)$，找出所有满足 $1\le x\le N$ 且 $\gcd (x,N)\ge M$ 的$x$的数量。

输入格式
第一行输入数据组数$T(T\le 100)$，每个数据输入两个整数$N,M$。

输出格式
对于每组样例，输出一个整数，表示满足条件的$x$的数量。

思路

暴力枚举 $\gcd (x,N)=d$ 多香啊！

定理：$N$的不同的约数个数是 $2\sqrt{n}-1$ 或 $2\sqrt{n}$。提示：$d$和$\frac{n}{d}$最多只有一个小于$\sqrt{n}$。

所以直接把$n$的约数处理出来，然后枚举这个$d$。

此时，设 $x=kd$，那么 $\gcd (x,N)=\gcd (k\times d,\frac{N}{d}\times d)=d\cdot \gcd (k,\frac{N}{d})$

所以$$\gcd (k,\frac{N}{d})=1$$

我们再求一下$k$的范围：$n\ge x=kd$，得到$$k\le \frac{N}{d}$$

这两点综合起来，发现$k$的不同的取值就是$\phi (\frac{N}{d})$。

于是输出就应该为$$\sum _{d|n,m\le d}\phi (\frac{n}{d})$$

代码

#include <cstdio>#include <iostream>#include <algorithm>#include <vector>using namespace std;inline int readint(){   	int a = 0, f = 1; char c = getchar();	for(; c<'0' or c>'9'; c=getchar())		if(c == '-') f = -1;	for(; '0'<=c and c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}const int MaxN = 1000000;bool isPrime[MaxN+1];int phi[MaxN+1];vector<int> primes;void sievePrime(int n){   	for(int i=2; i<=n; ++i)		isPrime[i] = true;	primes.clear(); phi[1] = 1;	for(int i=2; i<=n; ++i){   		if(isPrime[i]){   			primes.push_back(i);			phi[i] = i-1;		}		for(int j=0,len=primes.size(); j<len and 1ll*i*primes[j]<=n; ++j){   			isPrime[i*primes[j]] = false;			if(i%primes[j] == 0){   				phi[i*primes[j]] = phi[i]*primes[j];				break;			}			phi[i*primes[j]] = phi[i]*phi[primes[j]];		}	}}int getPhi(int n){   	int ppl = 1;	for(int d=2; 1ll*d*d<=n and n>MaxN; ++d){   		if(n%d == 0)			ppl *= (d-1), n /= d;		while(n%d == 0)			ppl *= d, n /= d;	}	if(n > MaxN) ppl *= (n-1);	else ppl *= phi[n];	return ppl;}vector<int> divide(int n){   	vector<int> ys; ys.clear();	for(int i=1; 1ll*i*i<=n; ++i)		if(n%i == 0){   			ys.push_back(i);			if(i != n/i)				ys.push_back(n/i);		}	sort(ys.begin(),ys.end());	return ys;}int main(){   	sievePrime(MaxN);	for(int T=readint(); T; --T){   		int n = readint(), m = readint();		int ans = 0;		vector<int> &&ys = divide(n);		for(vector<int>::iterator i=lower_bound(ys.begin(),ys.end(),m); i!=ys.end(); ++i)			ans += getPhi(n/(*i));		printf("%d\n",ans);	}	return 0;}