LuoguP2480「SDOI2010」题解

发表于

欧拉定理 + 中国剩余定理　+ Lucas定理

题目背景

“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”

——选自猪王国民歌

很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄园经济，很少与外界联系，商贸活动就更少了。因此也很少有其他动物知道这样一个王国。

猪王国虽然不大，但是土地肥沃，屋舍俨然。如果一定要拿什么与之相比的话，那就只能是东晋陶渊明笔下的大家想象中的桃花源了。猪王勤政爱民，猪民安居乐业，邻里和睦相处，国家秩序井然，经济欣欣向荣，社会和谐稳定。和谐的社会带给猪民们对工作火红的热情和对未来的粉色的憧憬。

小猪iPig是猪王国的一个很普通的公民。小猪今年10岁了，在大肥猪学校上小学三年级。和大多数猪一样，他不是很聪明，因此经常遇到很多或者稀奇古怪或者旁人看来轻而易举的事情令他大伤脑筋。小猪后来参加了全猪信息学奥林匹克竞赛(Pig Olympiad in Informatics, POI)，取得了不错的名次，最终保送进入了猪王国大学(Pig Kingdom University, PKU)深造。

现在的小猪已经能用计算机解决简单的问题了，比如能用P++语言编写程序计算出A + B的值。这个“成就”已经成为了他津津乐道的话题。当然，不明真相的同学们也开始对他刮目相看啦~

小猪的故事就将从此展开，伴随大家两天时间，希望大家能够喜欢小猪。

题目描述

猪王国的文明源远流长，博大精深。

iPig在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为N。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。

iPig打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的k分之一，其中k是N的一个正约数（可以是1和N）。不过具体是哪k分之一，以及k是多少，由于历史过于久远，已经无从考证了。

iPig觉得只要符合文献，每一种能整除N的k都是有可能的。他打算考虑到所有可能的k。显然当k等于某个定值时，该朝的猪文文字个数为N / k。然而从N个文字中保留下N / k个的情况也是相当多的。iPig预计，如果所有可能的k的所有情况数加起来为P的话，那么他研究古代文字的代价将会是G的P次方。

现在他想知道猪王国研究古代文字的代价是多少。由于iPig觉得这个数字可能是天文数字，所以你只需要告诉他答案除以999911659的余数就可以了。

输入输出格式

输入格式

输入文件ancient.in有且仅有一行：两个数N、G，用一个空格分开。

输出格式

输出文件ancient.out有且仅有一行：一个数，表示答案除以999911659的余数。

Input & Output’s examples

Input’s e.g. #1

1
4 2

Output’s e.g. #1

1
2048

分析

首先题意是让求这个式子的值：

$$G^{\sum_{d|n} C_n^d} \mod 999911659$$

根据欧拉定理的推论，并且$999911659$是一个质数，那么

$$G^{\sum_{d|n} C_n^d \mod 999911658} \mod 999911659$$

那么重点是要计算$\sum_{d|n} C_n^d \mod 999911658$,直接套$Lucas$定理肯定挂，那么我们尝试分解$999911658$

$$999911658 = 2 \times 3 \times 4679 \times 35617$$

那么分别计算出
$$\sum_{d|n} C_n^d \mod 2$$

$$\sum_{d|n} C_n^d \mod 3$$

$$\sum_{d|n} C_n^d \mod 4679$$

$$\sum_{d|n} C_n^d \mod 35617$$

这四个式子的值,并记为$a_1,a_2,a_3,a_4$。

然后联立出一个同余方程组：

ZWLqeg.png

然后求出一个最小正整数解$x$,快速幂求解$G^x \mod 999911659$即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 5e4 + 10;
const int mod = 999911658;
long long n,G,fac[MAXN],mos[5],value;
long long factor[5] = {0,2,3,4679,35617};
/* functions */
inline long long quick_power(long long a,long long b,long long p){
    long long ans = 1,base = a % p;
    while(b){
        if(b & 1) ans = ans * base % p;
        base = base * base % p; b >>= 1;
    }
    return ans;
}
inline long long C(long long n,long long m,long long p){
    if(m > n) return 0;
    return fac[n] * quick_power(fac[m] * fac[n-m],p-2,p) % p;
}
inline long long Lucas(long long n,long long m,long long p){
    if(m > n) return 0;
    if(!n) return 1;
    return C(n%p,m%p,p) * Lucas(n/p,m/p,p) % p;
}
inline void CRT(){
    FORL(i,1,4,1)
        value = (value + mos[i] * (mod/factor[i]) % mod * quick_power(mod/factor[i],factor[i]-2,factor[i])) % mod;
}
int main(int argc,char *argv[]){
    scanf("%lld%lld",&n,&G);
    if(G % (mod + 1) == 0){puts("0"); return 0;}
    FORL(i,1,4,1){
        fac[0] = 1;
        FORL(j,1,factor[i],1) fac[j] = fac[j-1] * j % factor[i];
        for(long long j=1;j*j<=n;j++){
            if(n % j == 0){
                mos[i] = (mos[i] + Lucas(n,j,factor[i])) % factor[i];
                if(j * j != n){
                    mos[i] = (mos[i] + Lucas(n,n/j,factor[i])) % factor[i];
                }
            }
        }
    }
    CRT();
    long long answer = quick_power(G,value,mod+1);
    printf("%lld\n",answer);
    return 0;
}

THE END