オープンも不参加でした。
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はハードル高いね。