首先，\(\varphi(n)\) 的值是 \(n\) 内与 \(n\) 互质的数的个数。
//求n的欧拉函数值： phi[n]
int getPhi(int n){
int ans = n;
for(int i = 2; i*i <= n; i++){
if(n % i == 0){
ans = ans * (i-1)/i;
while(n % i == 0) n /= i;
}
}
if(n > 1) ans = ans * (n-1)/n ;
return ans;
}
时间复杂度：sqrt(n)
你可能会问：你这玩意除了装X还有个【数据删除】用？
欸嘿还真不是，来了题你就知道了
T1
给定整数N和M，有多少整数X满足1<=X<=N且gcd（X，N）>=M？
第一行输入是一个整数T（T<=100），表示测试用例的数量。以下T行各包含两个数字N和M（2<=N<=100000000，1<=M<=N），表示一个测试用例。（注意这是个伏笔）
啊格式很丑大家别介意我从OJ上直接复制的...
首先 \(N\) 最多有 \(\sqrt n\) 个因数（说实话大多数时间达不到这个上限）
设 \(d\) 是 \(N\) 的约数，且 \(d>=M\)。
其实它起的不是约数的作用，而是这个最大公因数！因为不管咋样 \(\gcd(N,X)\mid N\)。
枚举它，问题就成了 \(1\) 到 \(\frac{d}{n}\) 有多少数和 \(\frac{d}{n}\) 互质（\(\frac{d}{n}\) 即 \(X\)）。
欸这好像是 \(\varphi(\frac{d}{n})\) 欸！
然后就水了，直接求和。
对了记得伏笔吗？这个 \(\varphi\) 不能线性筛求，得用它自己的计算公式。
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
LL phi(LL n)
{
LL sum=n;
for(LL i=2;i*i<=n;i++)
{
if(n%i==0)
{
sum=sum*(i-1)/i;
while(n%i==0)n/=i;
}
}
if(n>1)sum=sum*(n-1)/n;
return sum;
}
LL t,n,m,p[100010],o;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
LL sum=0;
o=0;
for(LL i=1;i*i<n;i++)
{
if(n%i==0)
{
p[++o]=i;
p[++o]=n/i;
}
}
LL s=sqrt(n);
if(s*s==n)p[++o]=s;
rep(i,1,o,1)
{
if(p[i]>=m)sum+=phi(n/p[i]);
}
cout<<sum<<endl;
}
return 0;
}