求歐拉函數(shù)

原題鏈接:AcWing 873. 歐拉函數(shù)

題目:給定n 個(gè)正整數(shù)a_{i}耕陷,請你求出每個(gè)數(shù)的歐拉函數(shù)仲吏。

歐拉函數(shù)1~N 中與 N 互質(zhì)的數(shù)的個(gè)數(shù)被稱為歐拉函數(shù)萎津,記為 ?(N)。公式如下:
?(N) = N(1-1/p_{1})(1-1/p_{2})...(1-1/p_n)
其中p_1, p_2, ..., p_nN的質(zhì)因子。
互質(zhì):兩個(gè)數(shù)的最大公因數(shù)是1经备,即gcd(a, b) = 1兼雄。

證明:

假設(shè)p,q,kN的質(zhì)因子,則在1~Np的倍數(shù)有p, 2p,3p,...,(N/p)p占业,一共N/p個(gè)绒怨。同理qk的倍數(shù)有N/q,N/k個(gè)。如果把這N/p,N/q,N/k個(gè)數(shù)去掉谦疾,則N/pq,N/pk, N/qk被多去了一次南蹂,需要加回來,但加回來后此時(shí)N/pqk被少去了一次念恍,所以需要再去掉一次六剥,故有在1~Np,q,k的倍數(shù)有:
\begin{aligned} S(N|p,q,k)&= N-(N/p+N/q+N/k) + (N/pq+N/pk+N/qk) - N/pqk\\ &= N(1-1/p)(1-/q)(1-1/k) \end{aligned}
故若N = p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}p_{1},p_{2},...,p_{n}N的質(zhì)因子峰伙,則1~Np_{1},p_{2},...,p_{n}的倍數(shù)有:
\begin{aligned} S(N|p_{1}, p_{2},...,p_{n})= N(1-1/p_{1})(1-/p_{2})...(1-1/p_{n}) \end{aligned}
而在1~N 中與 N 不互質(zhì)的只有其質(zhì)因子的倍數(shù)疗疟,所以與N互質(zhì)的數(shù)的個(gè)數(shù)即為1~N中非其質(zhì)因子倍數(shù)的個(gè)數(shù),從而有:
?(N) = N(1-1/p_{1})(1-1/p_{2})...(1-1/p_n)

算法實(shí)現(xiàn):

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        int res = x;
        for(int i=2;i<=x/i;i++)
        {
            if(x % i == 0)
            {
                res = res / i * (i - 1);
                while(x % i == 0) x /= i;
            }
        }
        if(x > 1) res = res / x  * (x - 1); // 先除再乘瞳氓,可以防止溢出
        
        cout << res << endl;
    }
    
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末策彤,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌店诗,老刑警劉巖叽赊,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異必搞,居然都是意外死亡必指,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進(jìn)店門恕洲,熙熙樓的掌柜王于貴愁眉苦臉地迎上來塔橡,“玉大人,你說我怎么就攤上這事霜第「鸺遥” “怎么了?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵泌类,是天一觀的道長癞谒。 經(jīng)常有香客問我,道長刃榨,這世上最難降的妖魔是什么弹砚? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮枢希,結(jié)果婚禮上桌吃,老公的妹妹穿的比我還像新娘。我一直安慰自己苞轿,他們只是感情好茅诱,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著搬卒,像睡著了一般瑟俭。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上契邀,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天摆寄,我揣著相機(jī)與錄音,去河邊找鬼蹂安。 笑死椭迎,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的田盈。 我是一名探鬼主播,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼缴阎,長吁一口氣:“原來是場噩夢啊……” “哼允瞧!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤述暂,失蹤者是張志新(化名)和其女友劉穎痹升,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體畦韭,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡疼蛾,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了艺配。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片察郁。...
    茶點(diǎn)故事閱讀 40,926評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖转唉,靈堂內(nèi)的尸體忽然破棺而出皮钠,到底是詐尸還是另有隱情,我是刑警寧澤赠法,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布肖爵,位于F島的核電站平斩,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜驻呐,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望嘉栓。 院中可真熱鬧迂尝,春花似錦、人聲如沸茂蚓。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽聋涨。三九已至晾浴,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間牍白,已是汗流浹背脊凰。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留茂腥,地道東北人狸涌。 一個(gè)月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像最岗,于是被迫代替她去往敵國和親帕胆。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容