【題解】UVA 10325 The Lottery

【題目敘述】https://vjudge.net/problem/UVA-10325
【解題想法】GCD, LCM, 排容原理

  • 【範例】N = 100,M = 3, a[3] = {3, 5, 7}
    • 3 的倍數有33個
    • 5 的倍數有20個
    • 7 的倍數有14個
    • {3, 5} 的LCM = 15,15的倍數有6個,要加回去
    • {5, 7} 的LCM = 35,35的倍數有2個,要加回去
    • {3, 7} 的LCM = 21,21的倍數有4個,要加回去
    • {3, 5, 7}的LCM = 105,105的倍數有0個,要扣除
    • 100 – (33 + 20 + 14) + (6 + 2 + 4) – 0 = 45
#include <iostream>
using namespace std;
#define ll long long

ll GCD(ll x, ll y){
    while ((x%=y) && (y%=x));
    return x+y;
}

ll LCM(ll x, ll y){
    return x/GCD(x,y)*y;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, M, cnt;
    ll ans, lcm;
    while (cin >> N >> M){
        ll a[M];
        for (int i=0; i<M; i++){
            cin >> a[i];
        }
        ans = 0;
        for (int i=1; i<(1<<M); i++){
            //枚舉M個數字取任意個數(cnt)的組合
            lcm = 1LL;
            cnt = 0;
            for (int j=0; j<M; j++){
                if (i & (1<<j)){
                    lcm = LCM(lcm, a[j]);
                    if (lcm > N) break;
                    cnt++;
                }
            }
            if (cnt % 2){
                //排容(奇數個因數)
                ans += N / lcm;
            } else {
                //排容(偶數個因數)
                ans -= N / lcm;
            }
        }
        cout << N - ans << "\n";
    }
    return 0;
}
分享本文 Share with friends