# CF 1295D 先算出 g = gcd(a,m) 要滿足此條件 a + x 必須為 g 的倍數 a + x 的 範圍為 [a, a + m) 算出這個範圍內 g 的倍數下界與上界 m 也除掉g ``` ll n, m; cin >> n >> m; ll ub = n + m - 1; ll lb = n; ll g = __gcd(n, m); lb /= g; ub /= g; m /= g; ``` 因為答案要求 gcd 為 g 符合答案的數不能再和 m 有其他公因數 題目變為在 [lower_bound,upper_bound] 有幾個和 m 互質的數 做此的其中一種方法為排容 先找出 m 的所有質因子 ``` vector<ll>fac; ll tmp = m; for(int i = 2 ; i <= sqrt(tmp) ; i++){ if(tmp % i)continue; while(tmp % i == 0){ tmp /= i; } fac.pb(i); } if(tmp > 1){ fac.pb(tmp); } ``` 接著算出範圍內有多少個數這些質因子皆不含 ex : m 有 2 和 3 兩個質因子 答案為 全部 - 2的倍數 - 3的倍數 + 2和3的倍數 ex : m 有 2 和 3 和 5三個質因子 答案為 全部 - 2的倍數 - 3的倍數 - 5的倍數 + 2和3的倍數 + 3和5的倍數 + 2和5的倍數 - 2和3和5的倍數 決定加或減取決於取了幾個質因子 奇數為減 偶數為加 利用 bitmask 枚舉所有 mask 並算出目前mask的公倍數數量 並利用 __builtin_popcount(mask)&1 來算要加或減 ``` for(int i = 0 ; i < (1 << sz) ; i++){ ll mul = 1; for(int j = 0 ; j < sz ; j++){ if((1<<j) & i){ mul *= fac[j]; } } ll low = (lb - 1)/ mul; // 最小的可以的前一個 ll up = ub / mul; // 可以的最後一個 if(__builtin_popcount(i)&1){ ans -= up - low; } else{ ans += up - low; } } ``` ``` #include<bits/stdc++.h> using namespace std; #define pb push_back #define ll long long #define maxn 1100005 #define fr(i,j,k) for(int i=j;i<k;i++) #define f(n) fr(i,0,n) #define f1(n) fr(i,1,n+1) #define ms(i) memset(i,0,sizeof(i)); #define ms1(i) memset(i,-1,sizeof(i)); #define F first #define S second const int mod = 1e9+7; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ ll n; cin >> n; ll m; cin >> m; ll ub = n + m - 1; ll lb = n; ll g = __gcd(n, m); lb /= g; ub /= g; m /= g; vector<ll>fac; ll tmp = m; for(int i = 2 ; i <= sqrt(tmp) ; i++){ if(tmp % i)continue; while(tmp % i == 0){ tmp /= i; } fac.pb(i); } if(tmp > 1){ fac.pb(tmp); } int sz = fac.size(); ll ans = 0; for(int i = 0 ; i < (1 << sz) ; i++){ ll mul = 1; for(int j = 0 ; j < sz ; j++){ if((1<<j) & i){ mul *= fac[j]; } } //cout << mul << ' ' <<lb - 1 << ' ' << ub << '\n'; ll low = (lb - 1)/ mul; ll up = ub / mul; //cout << up - low << '\n'; if(__builtin_popcount(i)&1){ ans -= up - low; } else{ ans += up - low; } } cout << ans << '\n'; } } ```