CF1878F Vasilije Loves Number Theory
首先约数个数是积性函数，题目中要求 $\gcd(n,a)=1$，所以 $a$ 和 $n$ 互质，$n=d(a)d(n)$ ,于是问题转化为 $n$ 是否整除 $d(n)$。
观察题目，$n$ 可能会非常大，但这也启发我们把它质因数分解来存储，而对于 $d(n)$ 直接用一个变量 $ans$ 存下来，考虑 $n\times x$ 之后 $ans$ 会有什么变化。
设操作前 $n=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$，则 $ans=(c_1+1)(c_2+1)\cdots(c_k+1)$，直接乘 $x$ 是不好算的，考虑把 $x$ 也拆成若干个质数依次计算，对于 $x$ 的每个质因子 $p_i$，$ans$ 会变成 $(c_1+1)(c_2+1)\cdots(c_i+2)\cdots(c_k+1)$，所以贡献是好计算的。
代码细节比较多，不太好写，实际实现可以用 map 存储每一位质因数的位置，对于操作 $2$ 直接记下开始的状态暴力 memset 即可，复杂度 $\mathcal O(q(\log n+\sqrt x))$。
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
int T,q,n,ans,prans,cnt,stcnt,all,pr[2001],st[2001],p[2001],now[2001];
map<int,int> mp1,mpr;
void mian()
{
read(T);int x,y;
while(T--)
{
read(n,q),ans=1,memset(st,0,sizeof(st)),mp1.clear(),mpr.clear(),cnt=0;
for(int i=2;i*i<=n;++i)
{
if(n%i==0)
{
pr[++cnt]=i,mpr[i]=cnt;
while(n%i==0)n/=i,++st[cnt];
ans*=(st[cnt]+1);
}
}
if(n!=1)pr[++cnt]=n,mpr[n]=cnt,st[cnt]=1,ans*=2;
stcnt=cnt,prans=ans,mp1=mpr,memcpy(now,st,sizeof(st)),memcpy(p,pr,sizeof(p));
while(q--)
{
read(x);
if(x==2)cnt=stcnt,ans=prans,mp1=mpr,memcpy(now,st,sizeof(now)),memcpy(p,pr,sizeof(pr));
else
{
read(y);
for(int i=2;i*i<=y;++i)
{
if(y%i==0)
{
if(!mp1[i])p[++cnt]=i,mp1[i]=cnt;
int pos=mp1[i];
while(y%i==0)ans+=ans/(now[pos]+1),++now[pos],y/=i;
}
}
if(y!=1)
{
if(!mp1[y])p[++cnt]=y,mp1[y]=cnt;
int pos=mp1[y];
ans+=ans/(now[pos]+1),++now[pos];
}
int flag=1,x=ans;
for(int i=1;i<=cnt;++i)
{
int sum=0;
while(x%p[i]==0)x/=p[i],++sum;
if(sum>now[i])flag=0;
}
if(x!=1)flag=0;
puts(flag?"yes":"no");
}
}
puts("");
}
}