GCD Again

忘是亡心i 2021-12-24 17:21 259阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td> <h1>GCD Again</h1> </td> 
  </tr> 
  <tr> 
   <td>Time Limit: 1000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp; Memory Limit: 32768/32768 K (Java/Others)</td> 
  </tr> 
  <tr> 
   <td>Total Submission(s): 193&nbsp; &nbsp; Accepted Submission(s): 112</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Problem Description 
    </div> 
    <div>
      Do you have spent some time to think and try to solve those unsolved problem after one ACM contest? No? Oh, you must do this when you want to become a "Big Cattle". Now you will find that this problem is so familiar: The greatest common divisor GCD (a, b) of two positive integers a and b, sometimes written (a, b), is the largest divisor common to a and b. For example, (1, 2) =1, (12, 18) =6. (a, b) can be easily found by the Euclidean algorithm. Now I am considering a little more difficult problem: Given an integer N, please count the number of the integers M (0&lt;M&lt;N) which satisfies (N,M)&gt;1. This is a simple version of problem “GCD” which you have done in a contest recently,so I name this problem “GCD Again”.If you cannot solve it still,please take a good think about your method of study. Good Luck! 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Input 
    </div> 
    <div>
      Input contains multiple test cases. Each test case contains an integers N (1&lt;N&lt;100000000). A test case containing 0 terminates the input and this test case is not to be processed. 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Output 
    </div> 
    <div>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;For each integers N you should output the number of integers M in one line, and with one line of output for each line in input. 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Sample Input 
    </div> 
    <div> 
     <pre>2
4
0</pre> 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Sample Output 
    </div> 
    <div> 
     <pre>0
1</pre> 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Author 
    </div> 
    <div>
      lcy 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Source 
    </div> 
    <div>
      2007省赛集训队练习赛（10）_以此感谢DOOMIII 
    </div> 
    <div>
      &nbsp; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Recommend 
    </div> 
    <div>
      lcy 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

/*
    题意：给出你一个数n，然后让你求出比n小的，并且不与n互质的数的个数
    
    初步思路：欧拉函数，用n减去欧拉函数-1
    */
    #include<bits/stdc++.h>
    using namespace std;
    /**************************欧拉函数模板*****************************/
    int euler(int n){
        int cur=n,i;
        for(i=2;i*i<=n;i++){
            /*
            怎么样保证每一个能被n整除的数都是素因子呐，比当前i大的数，肯定能找到一个素数，相乘等于n
            那么只需要每找到一个素数就把n中所有能和这个素数相乘等于n的数全部去除掉，那么这样就能满足
            要求了。
            */
            if(n%i==0){
                cur=cur-cur/i;
                while(n%i==0)
                    n/=i;
            }
        }
        if(n>1) cur=cur-cur/n;
        return cur;
    }
    /**************************欧拉函数模板*****************************/
    int n;
    int main(){
        // freopen("in.txt","r",stdin);
        while(scanf("%d",&n)!=EOF&&n){
            printf("%d\n",n-euler(n)-1);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wuwangchuxin0924/p/6233424.html