kmjp's blog

競技プログラミング参加記です

VK Cup 2015 Round 3 : D. Superhero's Job

本番は残念ながら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;
	
}

まとめ

シンプルな設定だけどなかなか面白かった。