洛谷P2480 古代豬文

2022-09-23 07:27:10 字數 1665 閱讀 3127

豬王國的文明源遠流長,博大精深。

ipig 在大肥豬學校圖書館中查閱資料,得知遠古時期豬文文字總個數為 \(n\)。當然,一種語言如果字數很多,字典也相應會很大。當時的豬王國國王考慮到如果修一本字典,規模有可能遠遠超過康熙字典,花費的豬力、物力將難以估量。故考慮再三沒有進行這一項勞豬傷財之舉。當然,豬王國的文字後來隨著歷史變遷逐漸進行了簡化,去掉了一些不常用的字。

ipig 打算研究古時某個朝代的豬文文字。根據相關文獻記載,那個朝代流傳的豬文文字恰好為遠古時期的 \(1/k\),其中 \(k\) 是 \(n\) 的一個正約數(可以是 \(1\) 或 \(n\))。不過具體是哪 \(1/k\),以及 \(k\) 是多少,由於歷史過於久遠,已經無從考證了。

ipig 覺得只要符合文獻,每一種 \(k|n\) 都是有可能的。他打算考慮到所有可能的 \(k\)。顯然當 \(k\) 等於某個定值時,該朝的豬文文字個數為 \(n/k\)。然而從 \(n\) 個文字中保留下 \(n/k\) 個的情況也是相當多的。ipig 預計,如果所有可能的 \(k\) 的所有情況數加起來為 \(p\) 的話,那麼他研究古代文字的代價將會是 \(g^p\)。

現在他想知道豬王國研究古代文字的代價是多少。由於 ipig 覺得這個數字可能是天文數字,所以你只需要告訴他答案除以 \(999911659\) 的餘數就可以了。

一句話題意:給出\(n,g\),求\(g^c^d_n}\ mod\ 999911659\)。

根據尤拉定理得

\[g^c^d_n}\ mod\ 999911659\ =\ g^c^d_n\ mod\ 999911658}\ mod\ 999911659

\]篩出\(n\)的每一個因子\(d\),考慮對於其中一個因子\(d[i]\)如何求\(c^_n\ mod\ 999911658\)

由於\(999911658=2\times 3\times 4679\times 35617\),考慮到質因子較小且個數較少,我們可以用\(lucas\)先求出\(a_1=c_n^\ mod\ 2,a_2=c_n^\ mod\ 3,a_3=c_n^mod\ 4679,a_4=c_n^\ mod\ 35617\),然後解同餘方程組

\[\left\x\equiv a_1(mod\ 2)\\ x\equiv a_2(mod\ 3)\\ x\equiv a_3(mod\ 4679)\\ x\equiv a_4(mod\ 35617)\end\right.

\]對於每一個因數\(d[i]\)我們都可以解除一個同於方程組的解\(x_i\)。最後答案就是\(g^x_i}\)

#include #include #include using namespace std;

typedef long long ll;

const int n=80010,mod=999911659;

const int v=;

int n,m,g,s,ans,d[n];

ll fac[n];

ll power(ll x,ll k,ll p)

ll c(int n,int m,int p)

ll lucas(int n,int m,ll p)

ll crt(int j)

int main()

for (int j=1;j<=4;j++)

printf("%lld",power(g,ans,mod));

return 0;

}

洛谷P2480 古代豬文

題目大意 求 g binom mod 999911659 題解 盧卡斯定理 中國剩餘定理 利用盧卡斯定理求出指數和式對各個素模數的解,再利用中國剩餘定理合併四個解即可。 也可以在列舉 n 的因子的過程中,對於計算的四個解直接進行中國剩餘定理的合併,答案不變。 如下 include using nam...

P2480 SDOI2010 古代豬文 題解

刷的最後一道數論題,喔,一聲長嘆 p2480 sdoi2010 古代豬文 今天還是來大致描述一下題面好了 給定 q n 1 q n 10 9 ,計算 q c d n mod 999911659 先考慮特殊情況,如果 q 是 999911659 的倍數,則答案為 0 否則,因為 999911659 是...

洛谷p2010 迴文日期

在日常生活中,通過年 月 日這三個要素可以表示出一個唯一確定的日期。 牛牛習慣用88位數字表示一個日期,其中,前44位代表年份,接下來22位代表月 份,最後22位代表日期。顯然 一個日期只有一種表示方法,而兩個不同的日期的表 示方法不會相同。 牛牛認為,一個日期是迴文的,當且僅當表示這個日期的8位數...