感觉要每天更新一条博客，来证明自己有在学习啊 QvQ
Description
scut.online 上的一道题
给定两个数 $n,m(1 \le m \le n \le 10^{12})$.
求满足 $1 \le x \le n$ 同时 $m \le gcd(x,n)$ 的 $x$ 的个数.
Solution
直接考虑枚举 $gcd(x,n)$，设 $gcd(x,n)=i$，那么符合条件的 $x$ 就是与 $\frac{n}{i}$ 互质的数，(回忆下欧拉函数的定义)，它的数量总共有 $\phi(\frac{n}{i})$ 个.
原题即转化为求 $\sum_{i \mid n,i \ge m}\phi(\frac{n}{i})$ 的值.
可以先预处理素数，然后对于每组样例都去枚举 $n$ 的所有约数，将对应的欧拉函数值加进答案即可.
AC code
好像跑的也没有很快的样子啊…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef pair<ll,int> pii;
const int maxn=1e6+5;
bool vis[maxn];
int prim[maxn];
int cnt;
ll n,m;
ll tn;
vector<pii> v;
ll ans=0;
void init() {
cnt=0;
for(int i=2;i<maxn;++i) {
if(!vis[i]) {
prim[++cnt]=i;
for(int j=2*i;j<maxn;j+=i) {
vis[j]=1;
}
}
}
}
void dfs(ll res,int index,ll phi) {
int len=v.size();
if(res>=m) {
ans+=phi;
}
for(int i=index+1;i<len;++i) {
ll p=v[i].fi;
int num=v[i].se;
ll k=1;
for(int j=1;j<=num;++j) {
k*=p;
dfs(res*k,i,j==num?phi/(p-1)*p/k:phi/k);
}
}
}
int main() {
init();
int caseCnt;
scanf("%d",&caseCnt);
while(caseCnt--) {
scanf("%lld%lld",&n,&m);
tn=n;
v.clear();
for(int i=1;i<=cnt;++i) {
if(n%prim[i]==0) {
int sum=0;
while(n%prim[i]==0) {
n/=prim[i];
sum++;
}
v.pb(mp(prim[i],sum));
}
}
if(n!=1) v.pb(mp(n,1));
ans=0;
ll phi=tn;
int len=v.size();
for(int i=0;i<len;++i) {
ll p=v[i].fi;
phi=phi/p*(p-1);
}
dfs(1,-1,phi);
printf("%lld\n",ans);
}
return 0;
}