sgu 102 Coprimes 解题报告及测试数据

102. Coprimes

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

题解：

求一个1-10000之间的数 N 的互质数个数。题目很简单，有两种方法：

1、复杂度是O(n^2)，依次判断从1到N-1的数是否与N互质。

2、复杂度是O(n)，换一种想法，先求与N不互质的数的个数，然后用N减去即可。例如9，从2开始循环，3与9不互质，那么3的倍数也与9不互质,所以6也与9不互质。因为N很小，所以可以开一个数组a[10005]，初始化为0，将与N不互质的位置标记为1，然后cnt++。

以下是代码（解法2）：

#include <iostream>

using namespace std;

int a[10005];

int main(){

    int n,cnt=1;//cnt初始化为1，即默认n与n不互质

    cin >> n;

    for(int i=2;i<n;i++)

    if(a[i]==0){  //如果i是n的因数，且未标记过

        if(n%i==0)

        for(int j=1;j*i<n;j++)//将所有i的倍数，标记为 1 ，cnt++

        if(a[i*j]==0){

            a[j*i]=1;

            cnt++;

        }

    }

    if(n==1)cout << "1"<<endl;

    else cout << n-cnt<<endl;   //n-cnt即是答案

}

以下是测试数据：

sample input

100

sample output

巴特西

sgu 102 Coprimes 解题报告及测试数据

最新文章

热门文章