杭电ACMsteps2.1.6解题报告#include<iostream>usingnamespacestd;intfun(intn);intmain(){intt,n,i,k;while(cin>>t){for(i=0;i<t;i++){cin>>n;k=fun(n);cout<<k<<endl;}}return0;}intfun(intn){inti,a;a=1;for(i=2;i*i<=n;i++)if(n%i==0){n=n/i;a=a*(i-1);while(n%i==0){n=n/i;a=a*i;}}if(n>1)a=a*(n-1);returna;}这个题的是实质是求一个数和比它小的正整数是否有公约数。如果有公约数，则为新朋友，否则为老朋友。我们可以把这个数除以这个正整数，然后的把除后的值又重新赋值给这个数，依次循环的进行下去，直到这个数模次正整数为不为0时，次正整数自加，然后又作上述循环，知道次正整数的平方比这个数的原始值大时，这个数比1还打，那么肯定无公约数，这个数即为新朋友。