K. Indivisibility ～余事象を包除原理で求める～

• Quiz
  • https://codeforces.com/problemset/problem/630/K
• AC
  • https://codeforces.com/contest/630/submission/100290959
• 解説
  • 余事象を包除原理で求める（下記画像参照）

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    ll all = N;
    ll a=0; // 余事象
    a += N/2;
    a += N/3;
    a += N/5;
    a += N/7;
    
    a -= N/(2*3);
    a -= N/(2*5);
    a -= N/(2*7);
    a -= N/(3*5);
    a -= N/(3*7);
    a -= N/(5*7);
    
    a += N/(2*3*5);
    a += N/(2*3*7);
    a += N/(2*5*7);
    a += N/(3*5*7);

    a -= N/(2*3*5*7);

    ll ans = N-a;
    p(ans);
    return 0;
}