让我们用d(n)表示数字n的所有约数之和，即d(n)=∑k|nk。
例如,d (1) = 1, d (4) = 1 + 2 + 4 = 7, d(6) = 1 + 2 + 3 + 6 = 12。
对于一个给定数字c，找出使d(n)=c的最小n。
我们考虑nlogn的预处理，然后每次询问O（1)
也就是需要一个logn的分解质因子的方法
我们在用欧拉筛素数的时候，顺便处理出每个数的最小质因子
然后我们质因子分解的时候，我们每个数除她的最小质因子求幂
这样最坏情况下logn的（逃）
然后分解完质因子考虑如何求所有因子的和
用这个公式就好了，等比数列求和然后相乘
ll qpow(ll a, ll b) { ll ans = 1; while(b) { // if(b & 1) ans = ans * a % mod; if(b & 1) ans = ans * a ; // a = a * a % mod; a = a * a ; b >>= 1; } return ans; } int x,p[10000002],vis[10000002],mi[10000002]; void oula() { for(int i=2 ; i<=10000001; i++) { if(vis[i]==0) p[++x] = i,mi[i]=i; for(int j=1 ; j<=x&&p[j]*i<10000002; j++) { vis[i*p[j]]=1; mi[i*p[j]] = p[j]; if(i%p[j]==0) break; } } } ll cal(ll x) { ll temp=1; while(x>1) { ll t = mi[x]; ll sum=0; while(x%t==0) x/=t,sum++; temp*=(qpow(t,sum+1)-1)/(t-1); if(temp>10000000) return 10000001; } return temp; } int c,a[10000002]; int main() { oula(); for(int i=1 ; i<=10000000 ; i++) { ll num = cal(i); if(num<=10000000) { if(a[num]==0) a[num] = i; else continue; } } int _ ; _ = read(); while(_--) { c=read(); if(a[c]) out(a[c]); else out(-1); puts(""); } return 0 ; }
1933ms(逃)
听说隔壁数论爷用狄利克雷前缀和400+就过了
Codeforces Round #713 (Div. 3)-G - Short Task（质因子分解）
原文：https://www.cnblogs.com/UpMing/p/14644575.html
