這個(gè)題目主要是求解最大公約數(shù)大于1的數(shù)目，采用歐拉函數(shù)來求解。通過逆向思維通過求與其互質(zhì)的數(shù)目，通過總數(shù)減去互質(zhì)的數(shù)目，再排除掉1這個(gè)數(shù)字。

歐拉函數(shù)如下：

????????????????????? ,其中p1, p2……pn為x的所有質(zhì)因數(shù)，x是不為0的整數(shù)。φ(1)=1（唯一和1互質(zhì)的數(shù)(小于等于1)就是1本身）。 (注意：每種質(zhì)因數(shù)只一個(gè)。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4。

#include<iostream>
using namespace std;
long long getNum(long long n)
{
?
?long long res = n;
?for (int i = 2; i*i <= n; i++)
?{
??if (n%i == 0)
??{
???res= res*(i - 1) / i;
??}
??while (n%i == 0)
??{
???n = n / i;
??}
}
?if (n >1)
??res = res*(n - 1) / n;
?
?return res;
}
int main()
{
?long long n;
?while (cin >> n)
?{
??if (n == 0)
???break;
??long long count = n - getNum(n) - 1;
??cout <<? count << endl;
?}
?return 0;
}

與50位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的GCD Again的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。