本番は残念ながらTLEしてしまった。
http://codeforces.com/contest/542/problem/D
問題
正の整数xに対し、J(x)はxの約数であるkのうち、kと(x/k)の最大公約数であるようなものの総和と定義する。
正整数Aが与えられる。J(x)=Aとなるxは何通りあるか求めよ。
解法
xを素数p1,p2...を用いてx = (p1^q1) * (p2^q2)...と素因数分解できたとする。
kの候補は、各素因数を完全に含むか含まないかの2通りなので、J(x) = (1 + p1^q1) * (1 + p2^q2) ... となる。
よって、Aを(1+p^q)の形の項の積で表せるか試していけば良い。
Aは10^12までと大きいので、まず10^6までの素数pを列挙し、p^q≦10^12の範囲で(1+p^q)の形を取り得る値を列挙しておこう。
あとはAの約数に対するdpで、上記(1+p^q)で約数をさらに割っていき、2~10^6の素数pに対し(1+p^q)で割ったときに取り得ず約数とその組み合わせを求める。
最終的に残った値は10^6を超える可能性があるが、それはそれぞれ(1+素数)の形を取るならば答えに計上すればよい。
const int prime_max = 1000001; int NP,prime[100000],divp[prime_max]; map<ll,int> M; ll A; ll from[10000],to[10000]; void cprime() { for(int i=2;i<prime_max;i++) if(divp[i]==0) { prime[NP++]=i; for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i; } } vector<ll> enumdiv(ll n) { vector<ll> S; for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); } sort(S.begin(),S.end()); return S; } bool isprime(ll v) { for(ll i=2;i*i<=v;i++) if(v%i==0) return false; return true; } void solve() { int i,j,k,l,r,x,y; string s; cprime(); cin>>A; auto D=enumdiv(A); FOR(i,D.size()) M[D[i]]=i; from[0]=1; FOR(i,NP) { memmove(to,from,sizeof(from)); ll a=prime[i]; while(a<A) { if(A%(1+a)==0) { FOR(x,D.size()) { ll v=D[x]*(1+a); if(M.count(v)) to[M[v]]+=from[x]; } } a*=prime[i]; } swap(from,to); } ll ret=from[D.size()-1]; FOR(i,D.size()-1) if(from[i]) { ll d=A/D[i]; if(d-1>=prime_max && isprime(d-1)) ret+=from[i]; } cout<<ret<<endl; }
まとめ
シンプルな設定だけどなかなか面白かった。