@[masterhuang](/user/365021) 不是双倍经验
by Adchory @ 2024-03-17 19:36:39
@[Adchory](/user/590600) 大佬能讲下那个题怎么做的吗，我不知道为啥 WA 掉了
by diqiuyi @ 2024-04-25 14:47:24
@[diqiuyi](/user/324666) https://www.luogu.com.cn/problem/SP14664
by Adchory @ 2024-04-25 14:54:50
@[Adchory](/user/590600) 但是都没有题解。。
能帮忙看看这个为啥是错的吗
```cpp
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
int t,p[5]={2,7,13,31,61},tot,k[20];
ll ans,n,pri[20];
ll gcd(ll x,ll y){
int xx=__builtin_ctzll(x),yy=__builtin_ctzll(y),zz=min(xx,yy);
y>>=yy;
while(x){
x>>=xx;
ll d=abs(x-y);
xx=__builtin_ctzll(d);
y=min(x,y),x=d;
}
return y<<zz;
}
ll mul(ll a,ll b,ll n){
return ((ull)a*b-(ull)((long double)a/n*b)*n+n)%n;
}
ll Pow(ll x,ll y,ll mod){
ll res=1;
for(;y;y>>=1,x=mul(x,x,mod))
if(y&1)
res=mul(res,x,mod);
return res;
}
bool check(ll n){
if(n<=65){
if(n==1) return 0;
for(int i=2;i*i<=n;i++)
if(!(n%i))
return 0;
return 1;
}
ll d,g;
for(int i=0;i<5;i++){
d=n-1,g=Pow(p[i],d,n);
if(g^1) return 0;
while((d&1)^1){
d>>=1,g=Pow(p[i],d,n);
if(g==n-1) break;
if(g^1) return 0;
}
}
return 1;
}
ll getd(ll n){
ll c=rand()*rand(),xl=c+1145141,x=xl,y=xl;
if(n<=20)
for(int i=2;i<=n;i++)
if(!(n%i))
return i;
x=(mul(x,x,n)+c)%n,y=(mul(y,y,n)+c)%n,y=(mul(y,y,n)+c)%n;
for(int lmt=1;x^y;lmt=min(lmt,64)){
ll cnt=1;
for(int i=1;i<=lmt;i++){
ll now=mul(cnt,abs(x-y),n);
if(!now) break;
cnt=now;
x=(mul(x,x,n)+c)%n,y=(mul(y,y,n)+c)%n,y=(mul(y,y,n)+c)%n;
}
ll d=gcd(cnt,n);
if(d>1) return d;
}
return 1;
}
vector<int> v;
void pr(ll x){
if(x<=1) return ;
if(check(x)){
v.push_back(x);
return ;
}
ll d=getd(x);
pr(d),pr(x/d);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
srand(time(0));
cin>>t;
while(t--){
cin>>n,v.clear(),tot=0,ans=1;
memset(k,0,sizeof(k));
pr(n);
for(int i=0;i<v.size();i++)
if(v[i]==pri[tot]) k[tot]++;
else pri[++tot]=v[i],k[tot]=1;
for(int i=1;i<=tot;i++)
if(pri[i]^2)
ans=1ll*ans*(k[i]*2+1);
else ans=1ll*ans*(2*k[i]-1);
// for(int i=1;i<=tot;i++)
// cout<<pri[i]<<' '<<k[i]<<'\n';
cout<<ans/2<<'\n';
}
return 0;
}
```
by diqiuyi @ 2024-04-25 16:38:41
@[diqiuyi](/user/324666) 结论给你
容易注意到 $p(n)=\begin{cases}\dfrac{\tau(n^2)}{2}&(n\in odd)\\\dfrac{\tau(\frac{n^2}{2})}{2}&(n\in even)\end{cases}$。
其中 $\tau(n)$ 表示 $n$ 的因子个数。
看到结论你应该就能理解了
by Adchory @ 2024-04-25 16:44:58
@[Adchory](/user/590600) 偶数的部分应该是 $\tau((\frac{n}{2})^2)$
by Adchory @ 2024-04-25 16:46:54
@[Adchory](/user/590600) 那我的写法有啥问题吗/yiw
by diqiuyi @ 2024-04-25 19:39:37
感觉等价啊
by diqiuyi @ 2024-04-25 19:40:03
@[diqiuyi](/user/324666) emm，你没排序啊，PR 随出来的因子不一定是从小到大的。
by Adchory @ 2024-04-25 19:59:46
@[Adchory](/user/590600) 卧槽，wssb
by diqiuyi @ 2024-04-25 20:38:01