题解
\(a,n\) 互质,所以 \(d(n·a)=d(a)d(n)\) ,即 \(n\ mod\ d(n)==0\) 是否成立。(总是能构造出一与 \(n\) 互质,且 \(d(a)\) 任意的 \(a\) )
由于 \(n\) 会很大,所以我们将 \(n\) 质因子分解,\(n=p_1^{m_1}p_2^{m_2}...p_k^{m_k}\)
这样一来 \(d(n)=(m_1+1)(m_2+1)...(m_k+1)\)
乘 \(x\) 的时候,将 \(x\) 也进行质因子分解
最后在判断 \(d(n)\) 进行质因子分解,然后判断因子是否足够
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool mark[1000006]={0};
int prime[1000006];
void solve()
{
int n,q;
cin>>n>>q;
int tem=n;
map<int,int> yz;
while(n!=1)
{
yz[prime[n]]++;
n/=prime[n];
}
while(q--)
{
int op;
cin>>op;
if(op==2)
{
yz.clear();
n=tem;
while(n!=1)
{
yz[prime[n]]++;
n/=prime[n];
}
}
else
{
int x;
cin>>x;
while(x!=1)
{
yz[prime[x]]++;
x/=prime[x];
}
ll ans=1;
for(auto it:yz)
{
ans*=(it.second+1);
}
bool flag=1;
for(ll i=2;i*i<=ans;i++)
{
if(ans%i==0)
{
int cnt=0;
while(ans%i==0)
{
ans/=i;
cnt++;
}
if(yz[i]<cnt)
{
flag=0;
break;
}
}
}
if(ans>1)
{
if(yz[ans]<1) flag=0;
}
if(flag) cout<<"yes\n";
else cout<<"no\n";
}
}
cout<<'\n';
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
for(ll i=2;i<=1e6;i++)
{
if(!mark[i])
{
prime[i]=i;
for(ll j=i*i;j<=1e6;j+=i)
{
if(!mark[i])
{
prime[j]=i;
mark[j]=1;
}
}
}
}
int t;
cin>>t;
while(t--) solve();
return 0;
}
标签:prime,int,Vasilije,Number,cin,while,yz,Loves,ans
From: https://www.cnblogs.com/pure4knowledge/p/18294600