Lang:G++
Edit12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;#define ll long longll a[50],b[1010]; //a数组用来保存n的质因子,其中a[0]表示质因子个数void finds(ll n) //查找n的质因子个数{ll i,j=0;for(i=2; i*i<=n; ++i)if(n%i==0){while(n%i==0 )n/=i;a[++j]=i;}if(n>1) a[++j]=n;a[0]=j;}ll num(ll n) //根据容斥原理来判断Search中的mid含有多少个与n互质的数{ll g=0,sum=n,i,j,t;b[++g]=1;for(i=1; i<=a[0]; i++){t=g;for(j=1; j<=g; j++)b[++t]=b[j]*a[i]*(-1),sum+=n/b[t];g=t;}return sum;}