lay_contest beta round 00001 : D - 素

ひっかけのCに比べると直球な問題。
https://www.hackerrank.com/contests/lay-contest-00001/challenges/challenge-382

問題

2正整数X,Nが与えられる。
N以下の正整数のうち、Xと互いに素なものの数を答えよ。

解法

包除原理で解く。
Xの素因数をとする。
1～nの部分列として構成される数列iに対し、1～Nのうちでのすべてで割れ、残りの素因数で割れない正整数の数は個なので、kの偶奇に応じてこの値を加減算しよう。
あとは数列iの選び方(2^n)通りを列挙すればよい。

int T;
ll X,N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X>>N;
		
		vector<ll> V;
		for(ll i=2;i*i<=X;i++) if(X%i==0) {
			V.push_back(i);
			while(X%i==0) X/=i;
		}
		if(X>1) V.push_back(X);
		
		ll num=0;
		for(int mask=0;mask<(1<<V.size());mask++) {
			int sgn=1;
			ll x=1;
			FOR(i,V.size()) if(mask & (1<<i)) x *= V[i], sgn=-sgn;
			num += sgn*(N/x);
		}
		cout<<num<<endl;
	}
}

まとめ

なぜここでこんな定番問題を入れてきたのだろう？