10299:Relatives

問題文
http://uva.onlinejudge.org/external/102/10299.html

1以上でnより小さい、nと互いに素な数の個数を求めよ。

包除原理。
互いに素であるという事は共通素因数を持たないということ。
1からn-1のなかでこのような数の個数を求めればよい。
例えばn=30のとき、30=2*3*5だから1から29のなかで2も3も5も素因数に持たない数を数えればよい。
1から29までの整数で、
2の倍数の個数は29/2=14
3の倍数の個数は29/3=9
5の倍数の個数は29/5=5
2*3=6の倍数の個数は29/6=4
3*5=15の倍数の個数は29/15=1
2*5=10の倍数の個数は29/10=2
2*3*5=30の倍数の個数は29/30=0
よって、求める個数は
29-(14+9+5-(4+1+2-0))=8

nを素因数分解する。
素因数の種類はそれほど多くはならないので、どの素因数を使うかをビットで管理して↑のようなことをすればよい。

#include<iostream>
#include<vector>
#include<algorithm>

#define all(c) (c).begin(),(c).end()

using namespace std;

vector<int> prime_factor(int n){
  vector<int>res;
  for(int i=2;i*i<=n;i++){
    if(n%i==0)res.push_back(i);
    while(n%i==0)n/=i;
  }
  if(n!=1)res.push_back(n);
  return res;
}

int main(void){
  int n;

  while(cin >> n,n){
    vector<int>a=prime_factor(n);
    int ans=n-1,al=a.size();
    for(int S=1;S<(1<<al);S++){
      int cnt=0,tmp=1;
      for(int i=0;i<al;i++){
        if(S>>i&1)cnt++,tmp*=a[i];
      }
      if(cnt%2)ans-=(n-1)/tmp;
      else ans+=(n-1)/tmp;
    }
    cout << ans << endl;
  }
  return 0;
}