# 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';
}
}
```