[十二省聯(lián)考 2019] 騙分過樣例 題解 part 1

太多了，分兩天，但我不會原根，而且原根部分意思不大，只有最后一個猜模數(shù)還是類似暴力，就不寫了。

1. 發(fā)現(xiàn)增長很快，可以猜測和冪次或階乘有關，除一下前幾個，結合題目可以發(fā)現(xiàn)是 \(19^x \bmod 998244353\)，暴力即可。

2. 和一一樣，唯一需要的就是快速冪。

3. 和一一樣，但發(fā)現(xiàn)讀入巨大，用歐拉定理手寫快讀邊讀邊模即可。

4. 可以猜測和一類似，發(fā)現(xiàn)前兩個一樣，但模數(shù)明顯不同，考慮模數(shù)大概率是質(zhì)數(shù)，直接枚舉即可。

5. 猜測和四類似，發(fā)現(xiàn)模數(shù)出其的大。

   好像是最難的點，可以考慮用兩個接近的數(shù)并且小的答案大于大的，有模數(shù)是 \(ans_x\times 19^{y-x} -ans_y\) 的因數(shù)，雖然很大，但考慮范圍有限，還是能很快求出。

   但是我們有 python！！！

   我們發(fā)現(xiàn)，數(shù)據(jù)中有兩個極小的值，大約在 \(2000 \sim 5000\)，用 python 直接跑出答案，減掉 \(ans\) 就是模數(shù)倍數(shù)，求 \(\gcd\) 即可。

6. 發(fā)現(xiàn)題目中有一個 wa ，發(fā)現(xiàn)有負數(shù)，可以猜到是取模不及時導致的溢出，嘗試幾種溢出可知是暴力算的時候取模不及時，直接暴力即可。

7. 發(fā)現(xiàn)數(shù)據(jù)巨大，根本無法暴力，因為有溢出，不能快速冪。

   考慮對 \(2^{32}\) 取模后對 \(998244353\) 取模，應該有一個較小的循環(huán)節(jié)，數(shù)據(jù)證明只有 \(45699\) 個數(shù)，和一段頭，直接暴力整就好。