D. Count GCD
这道题严格来讲不难，a[i]与b[i+1]最大公约数为a[i+1],所以a[i]与b[i+1]必定整除a[i+1]，且a[i]/a[i+1]与b[i+1]/a[i+1]互质，所以我们只需要求1~m/a[i+1]中与a[i]/a[i+1]互质的数的个数。
网上看了一些代码，觉得难以理解，决定自己动手写一篇。
容斥原理：要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。
证明：二项式定理
若n为奇数，则令x=-1，y=1;
若n为偶数，则令x=1，y=-1;
可求得：
分解质因数：根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。
n=p1^a1 * p2^a2 *p3^a3.....pn^an
代码参上
#include<iostream>#include<algorithm>using namespace std;typedef long long ll; const int maxn=1e6+100; /*利用容斥原理，先求不互质的个数 ans，最后结果 n-ans。假如 m 有 2，3，5质因子，那么2， 3， 5的倍数与 m都不互质，但是会有重复。用容斥原理算出正确的即可。k / 2 + k / 3 + k / 5 - k / (2 * 3) - k / (3 * 5) - k / (2 * 5) + k / (2 * 3 * 5)出现奇数次的加，出现偶数次的减。代码枚举所有质因子的组合时用二进制枚举。*///先求m的因子，存放到p数组里ll n,m,cnt,p[maxn];void get_factor(ll m){cnt=0;for(int i=2;i*i<=m;i++){if(m%i==0){p[cnt++]=i;while(m%i==0){m/=i;} }}if(m>1){p[cnt++]=m;}} ll solve(ll n){ll ans=0;//二进制枚举for(int i=1;i < (1 << cnt);i++){ll temp=1,t=0;for(int j=0;j<cnt;j++){if((1<<j)&i){temp*=p[j];t++;}}if(t%2==1){ans+=n/temp;}else{ans-=n/temp;}}return n-ans;}int main(){scanf("%d%d",&n,&m);get_factor(m);cout<<solve(n)<<endl;}
如果觉得《关于求1~n中与m互质的数的个数（容器原理+数论分解质因子）》对你有帮助，请点赞、收藏，并留下你的观点哦！
