题目

“在那山的那边海的那边有一堆小肥猪。他们生气勃勃又聪慧,他们调皮又利落。他们自由自在生活在那暗紫的大草坪,他们善良勇敢相互都关注……”
——选自猪王国歌谣
很久自古以来,在山的那边海的那里的某片八字宝地曾经存在过一个猪王国。猪王国地理地方偏僻,实施的是适应当时社会的自给自足的园林经济,很少与外面交换,商业贸易活动就更加少了。因而也很少有此外动物知道这么贰个帝国。
猪王国尽管非常小,可是土地肥沃,屋舍简直。借使一定要拿什么与之相比较来说,那就只可以是西夏陶渊明笔下的望族想像中的桃花源了。猪王勤政爱民,猪民安居乐业,邻里和睦相处,国家秩序井然,经济蓬勃,社会协调安定。和谐的社会带给猪民们对工作火红的热忱和对前景的中黄的向往。
小猪iPig是猪王国的二个很一般的全员。小猪二〇一九年八虚岁了,在大肥猪高校上小学三年级。和大多数猪1样,他不是很掌握,因而平时遇上不少或然稀奇古怪只怕旁人看来轻而易举的政工令她大伤脑筋。小猪后来参预了全猪新闻学奥林匹克比赛(Pig
Olympiad in Informatics,
POI),取得了不错的排名,最后保送进入了猪王国民代表大会学(Pig Kingdom University,
PKU)深造。
未来的小猪已经能用总计机消除简单的难题了,比如能用P++语言编写程序总括出A
+
B的值。那么些“成就”已经济体改成了她津津乐道的话题。当然,不明真相的同室们也开端对她爱慕啦~
小猪的轶事就将从此展开,伴随大家两日时间,希望大家能够喜欢小猪。
标题描述 猪王国的雍容源源不断,博大精深。
iPig在大肥猪高校体育场地中查阅资料,得知远古一代猪文文字总个数为N。当然,1种语言假诺字数很多,字典也呼应会非常大。当时的猪王国国君思考到假若修一本字典,规模有非常大可能远远当先玄烨字典,开销的猪力、物力将难以猜想。故考虑再三没有举办那1项劳猪伤财之举。当然,猪王国的文字后来趁着历史转变慢慢开始展览了简化,去掉了有个别不常用的字。
iPig打算探讨南梁有个别朝代的猪文文字。依据相关文献记载,那多少个朝代流传的猪文文字恰好为远古一时的k分之1,当中k是N的贰个正约数(能够是一和N)。可是具体是哪k分之1,以及k是多少,由于历史过于久远,已经无法考证了。
iPig觉得固然顺应文献,每1种能整除N的k都以有望的。他打算思念到全体希望的k。明显当k等于有个别定值时,该朝的猪文文字个数为N
/ k。然而从N个文字中保留下N /
k个的情事也是一定多的。iPig揣度,要是具有十分的大希望的k的全体意况数加起来为P的话,那么她讨论古代文字的代价将会是G的P次方。
以往他想知道猪王国探究秦朝文字的代价是有点。由于iPig觉得那一个数字恐怕是天文数字,所以您只要求告诉她答案除以99991165玖的余数就足以了。

输入格式

有且仅有一行:五个数N、G,用1个空格分开。

输出格式

有且仅有1行:一个数,表示答案除以99991165玖的余数。

输入样例

4 2

输出样例

2048

提示

一成的多少中,一 <= N <= 50;
十分二的数量中,一 <= N <= 1000;
五分二的数额中,一 <= N <= 一千00;
百分之百的数据中,一 <= G <= 一千000000,壹 <= N <= 壹仟000000。

题解

一句话题意:

id=”MathJax-Element-861-Frame” class=”MathJax”>

正是神级标题,模数设计得非凡都行,综合了无数知识,供给处理的底细也不少

鉴于999911659是1个质数,利用费马小定理

枚举出N的拥有因子,逐壹算出其重组数相加
N相当大,总括组合数便相当艰巨,不可能间接算,思量Lucas定理

而是Lucas定理须求模为素数,99991165捌不满意须求,大家将其因式分解,获得贰,三,4679,356一7,有很好的品质便是每一种质因子都极小而且指数都为一

咱俩就足以分别算模各种因子的意况下的结果,末了用中中原人民共和国剩余定理总和到手拉手算出最后的结果

商贸公司,Lucas算组合数时能够先预处理各种模意义下的阶乘和逆元阶乘

末尾要留意当G也许等于P,这时正是0啦。
设若直接算恐怕会出贰个数额驱动指数为0,那样快捷幂就会算出1来

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
const int P = 999911659,PP = 999911658;
LL N,G,ans[5];
LL prime[4]={2,3,4679,35617},f[4][35618],inv[4][35618];
void init(){
    for (LL i = 0; i < 4; i++){
        LL p = prime[i];
        f[i][0] = 1;
        for (LL j = 1; j < p; j++) f[i][j] = f[i][j - 1] * j % p;
        inv[i][1] = 1;
        for (LL j = 2; j < p; j++) inv[i][j] = (p - p / j) * inv[i][p % j] % p;
        inv[i][0] = 1;
        for (LL j = 1; j <= p; j++) inv[i][j] = inv[i][j] * inv[i][j - 1] % p;
    }
}
LL qpow(LL a,LL b,LL Mod){
    LL ans = 1;
    for (; b; b >>= 1,a = (LL)a * a % Mod)
        if (b & 1) ans = (LL)ans * a % Mod;
    return ans;
}
void exgcd(LL a,LL b,LL& d,LL& x,LL& y){
    if (!b) {x = 1; y = 0; d = a;}
    else exgcd(b,a % b,d,y,x),y -= (a / b) * x;
}
LL Lucas(LL n,LL m,LL i){
    if (n < m) return 0;
    if (n < prime[i] && m < prime[i]) return f[i][n] * inv[i][m] % prime[i] * inv[i][n - m] % prime[i];
    return Lucas(n % prime[i],m % prime[i],i) * Lucas(n / prime[i],m / prime[i],i) % prime[i];
}
void cal(LL x){
    for (int i = 0; i < 4; i++)
        ans[i] = (ans[i] + Lucas(N,x,i)) % prime[i];
}
LL China(){
    LL a,b,d,x,y,Ans = 0;
    for (LL i = 0; i < 4; i++){
        exgcd(a = PP / prime[i],b = prime[i],d,x,y);
        x = (x % PP * (PP / prime[i]) % PP + PP) % PP;
        Ans = (Ans + ans[i] * x % PP) % PP;
    }
    return (Ans % PP + PP) % PP;
}
int main(){
    //freopen("in.txt","r",stdin);  
    //freopen("out1.txt","w",stdout);  
    init();
    cin>>N>>G; LL i;
    if (G == P) {puts("0"); return 0;}
    for (i = 1; i * i < N; i++)
        if (N % i == 0) cal(i),cal(N / i);
    if (i * i == N) cal(i);
    ans[5] = qpow(G % P,China(),P);
    cout<<ans[5]<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图