みんなのプロコン 2018 決勝 : A - Uncommon

オープンも不参加でした。
https://beta.atcoder.jp/contests/yahoo-procon2018-final-open/tasks/yahoo_procon2018_final_a

問題

整数の集合が与えられる。
1～Mの各整数について、元の集合の要素のうち、その値と互いに素であるものの数を求めよ。

解法

まず、各整数vに対し、元の集合に対しvの倍数がいくつあるかを求めておこう。
後はvを素因数分解し、包除原理の要領でvと素であるものを数え上げていく。

int N,M;
int cnt[101010];
int num[101010];

vector<ll> enumdiv(ll n) {
	vector<ll> V;
	for(ll 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);
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>x, cnt[x]++;
	
	for(i=1;i<=M;i++) {
		for(j=i;j<=100000;j+=i) num[i]+=cnt[j];
		
		vector<ll> D=enumdiv(i);
		ll ret=0;
		for(int mask=0;mask<1<<D.size();mask++) {
			int d=1;
			FOR(j,D.size()) if(mask&(1<<j)) d*=D[j];
			if(__builtin_popcount(mask)%2==0) ret+=num[d];
			else ret-=num[d];
		}
		cout<<ret<<endl;
	}
}

まとめ

わりと典型っぽいが、オンサイトで1問目から600ptはハードル高いね。