Codeforces ECR #037 : G. List Of Integers

いつものECR最終問題よりは楽。
http://codeforces.com/contest/920/problem/G

問題

数列L(x,p)を、xより大きいyのうちpと互いに素なものを小さい順に並べたものとする。
x,p,kが与えられるので、L(x,p)のうちk番目の要素を求めよ。

解法

F(p) = L(0,p)とする。
x以下の正整数のうちpと互いに素なものをz個とすると、求める解は結局F(p)のz+k番目の値である。
zはトーシェント関数で求めればよいし、後者のF(p)の特定の位置の値も、トーシェント関数を用いて二分探索すればよい。

int T;
int X,P,K;
vector<int> ps;

vector<int> enumpr(int n) {
	vector<int> V;
	for(int i=2;i*i<=n;i++) if(n%i==0) {
		V.push_back(i);
		while(n%i==0) n/=i;
	}
	if(n>1) V.push_back(n);
	sort(V.begin(),V.end());
	return V;
}

ll count(ll a,vector<int>& ps) {
	ll ret=0;
	int n=ps.size(),mask,i;
	FOR(mask,1<<n) {
		int s=1,sg=1;
		FOR(i,n) if(mask&(1<<i)) s*=ps[i], sg=-sg;
		ret+=sg*(a/s);
	}
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X>>P>>K;
		ps=enumpr(P);
		K+=count(X,ps);
		ll ret=1LL<<62;
		for(i=61;i>=0;i--) if(count(ret-(1LL<<i),ps)>=K) ret-=1LL<<i;
		cout<<ret<<endl;
		
	}
}

まとめ

なんなんだこれ？