n特別大,我們肯定不能枚舉每個(gè)數(shù)

我們思考一下

9e18 < 2² * (2e6)³

那么要枚舉b就行了

我們枚舉一發(fā)b,然后對(duì)于所有的b直接統(tǒng)計(jì)有多少a(利用sqrt)

唉為啥我Sample跑出來(lái)不對(duì),3e6跑出來(lái)為啥比答案大一點(diǎn)

我們經(jīng)過(guò)觀察,可以發(fā)現(xiàn)

我們似乎重復(fù)統(tǒng)計(jì)了一些東西

比如

4³ * 27² = 9³ * 8²

那么我們?cè)趺崔k?

我的做法是,如果b帶有平方因子,那么就忽略掉b的任何計(jì)算

這樣我們就統(tǒng)計(jì)出所有b不帶平方因子的個(gè)數(shù)

那么如果b帶平方因子,為了不重復(fù),它只能是一個(gè)質(zhì)數(shù)的平方

例如4,9,25是可以的,8,18,16等都是不行的

我們可以化簡(jiǎn),例如16³?* a²?= 4³?* (8a)²

但是4³ * 27² 也同樣化簡(jiǎn)就會(huì)變成這個(gè)樣子:

1³ * (8*27)²

所以我們只有4³?* 27²這種沒(méi)有統(tǒng)計(jì),其他的我們都統(tǒng)計(jì)過(guò)了,而且沒(méi)有重復(fù)的統(tǒng)計(jì)過(guò)了

那么這里我只能容斥來(lái)做了,統(tǒng)計(jì)有多少個(gè)合法的解

因?yàn)橹暗淖龇?(2*3)⁶就被統(tǒng)計(jì)了2次,而(2*3*5)⁶就被統(tǒng)計(jì)了3次,這里就需要容斥處理掉這些

甚至這個(gè)4*(2*3)⁶也被統(tǒng)計(jì)了2次,一次是4³ * 54²,一次是9³ * 16²

那么我們只能用容斥,對(duì)于每一個(gè)東西的6次方做容斥

當(dāng)然6次方還在n范圍內(nèi)的不多,可以處理好

代碼丟家里系列,下次回家補(bǔ)....

轉(zhuǎn)載于:https://www.cnblogs.com/absi2011/p/9480280.html

總結(jié)

以上是生活随笔為你收集整理的Project Eular 634的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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