1 void Solve(LL n){   ///分解质因数保存结果于p 2     p.clear(); 3     for(LL i=2; i*i<=n; i++) 4         if(n%i==0){ 5             p.push_back(i); 6             while(n%i==0) n/=i; 7         } 8     if(n>1) p.push_back(n); 9 }10 11 void dfs(LL k,LL t,LL s,LL n){ ///求与n互素个数12     if(k==p.size()){13         if(t&1) ans-=n/s;14         else    ans+=n/s;15         return;16     }17     dfs(k+1,t,s,n);18     dfs(k+1,t+1,s*p[k],n);19 }20 ///主函数内是:21 dfs(0,0,1,r);