昨天学习了欧拉，今天就来做了道欧拉的题目吧，这题有欧拉，还有运用到一个数学得知识--假设i与n互质，则n*自然数+i与n也是互质的，这样就能先找出与n互质的所有小于n的数字，然后后面就是一个循环，只是会按n*k（k=0,1,2,3,。。。）+i这种规律下去，只要求求就好了， 不过要注意他在第几个循环是比较麻烦的，人家指导我在求第几个循环的时候k要减一再除，就过了。。。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 int s[1000100]; 6 int dp[1000100],dpn; 7 long k,m; 8 void prime()//欧拉 9 {10     int i,j;11     memset(s,0,sizeof(s));12     s[1]=1;13     /*for(i=2;i<=1000000;i++)14         s[i]=i;*/15     for(i=2;i<=1000000;i++)16     {17         if(!s[i])18         {19          s[i]=i-1;20          j=i+i;21          while(j<=1000000)22          {23             if(!s[j])24                 s[j]=j;25             s[j]=s[j]/i*(i-1);26             j+=i;27          }28         }29     }30     return ;31 }32 33 int dpit()//找出所有互质的数字34 {35     int i,j;36     memset(dp,0,sizeof(dp));37     for(i=2;i<=m;i++)38     {39         j=i;40         if(!dp[i]&&m%i==0)41             while(j<=m)42             {43                 dp[j]=1;44                 j+=i;45             }46     }47     return 0;48 }49 int main()50 {51     prime();52     while(scanf("%ld%ld",&m,&k)!=EOF)53     {54             long a,b,t=0,x;55         dpn=0;56         a=(k-1)/s[m];57         b=k%s[m];58         if(!b)b=s[m];59         dpit();60         for(x=1;x<=m;x++)61         {62             if(!dp[x])63                 t++;64             if (t==b)65             {66                 a=m*a+x;67                 printf("%ld\n",a);68                 break;69             }70         }71     }     72     return 0;73 }