@ivorysi 2018-01-02T08:58:46.000000Z 字数 37108 阅读 965

数论学习笔记

笔记

素数

POJ 2689 Prime Distance

Description

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).

Input

Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.

Output

For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.

Sample Input

2 17
14 17

Sample Output

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

题解

由于l和u的范围不超过1000000，我们只要筛一个小区间的素数就行了
找出 $\sqrt u$ 范围的素数，然后从l/prime u/prime 开始筛
注意左边界必须是2
然后还有就是注意1 2 这样的数据

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 4000005
#define mod 51123987
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int l,z;
int prime[500006],tot;
bool nonprime[1000006];
void solve() {
    memset(nonprime,0,sizeof(nonprime));
    if(l==1) l=2;
    siji(i,1,tot) {
    int s=l/prime[i],t=z/prime[i];
    s=max(s,2);
    if(s>t) break;
    siji(j,s,t) {
        if(j*prime[i]<l)continue;
        nonprime[j*prime[i]-l]=1;
    }
    }
    int last=-1;
    int c1=-1,c2=1000001,d1=0,d2=0;
    siji(i,0,z-l) {
    if(!nonprime[i] && last==-1) last=i;
    else if(!nonprime[i]) {
        if(i-last < c2-c1) {
        c1=last+l;
        c2=i+l;
        }
        if(i-last > d2-d1) {
        d1=last+l;
        d2=i+l;
        } 
        last=i;
    }
    }
    if(c1==-1) {
    puts("There are no adjacent primes.");
    }
    else {
    printf("%d,%d are closest, %d,%d are most distant.\n",c1,c2,d1,d2);
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    siji(i,2,1000000) {
    if(!nonprime[i]) {
        prime[++tot]=i;
        siji(k,2,1000000) {
        if(i>1000000/k) break;
        nonprime[i*k]=1;
        }
    }
    }
    while(~scanf("%d%d",&l,&z)) {
    solve();
    }
    return 0;
}

素因子分解

POJ 3421 X-factor Chains

Description

Given a positive integer X, an X-factor chain of length m is a sequence of integers,
1 = X0, X1, X2, …, Xm = X
satisfying
Xi < Xi+1 and Xi | Xi+1 where a | b means a perfectly divides into b.
Now we are interested in the maximum length of X-factor chains and the number of chains of such length.

Input

The input consists of several test cases. Each contains a positive integer X (X ≤ $2^{20}$ ).

Output

For each test case, output the maximum length and the number of such X-factors chains.

Sample Input

2
3
4
10
100

Sample Output

1 1
1 1
2 1
2 2
4 6

题解

这道题就是素因子分解，因为如果两个相邻的数之间的乘积不是质数那么还可以更长
数目就是这些素因子的排列方法，就是一个带重复元素的全排列

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 4000005
#define mod 51123987
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int prime[1000005],tot,n;
bool nonprime[2000005];
ll dp[2000005],ti[2000005],fac[25];
void calc(int l,int z) {
    if(l>=z) return;
    if(dp[l]+1 > dp[z]) {
    dp[z]=dp[l]+1;
    ti[z]=ti[l];
    }
    else if(dp[l]+1==dp[z]) {
    ti[z]+=ti[l];
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    siji(i,2,2000000) {
    if(!nonprime[i]) {
        prime[++tot]=i;
        dp[i]=1;ti[i]=1;
        siji(k,2,2000000) {
        if(i>1000000/k) break;
        nonprime[i*k]=1;
        }
    }
    }
    fac[0]=1;
    siji(i,1,20) {
    fac[i]=fac[i-1]*i;
    }
    while(scanf("%d",&n)!=EOF) {
    int cnt=0;
    ll tmp=1;
    siji(j,1,tot) {
        if(n<prime[j]) break;
        int z=0;
        while(n%prime[j]==0) {
        n/=prime[j];
        ++z;
        ++cnt;
        }
        tmp*=fac[z];
    }
    if(n!=1) ++cnt;
    printf("%d %lld\n",cnt,fac[cnt]/tmp);
    }
    return 0;
}

POJ 3090 Visible Lattice Points

Description

A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 ≤ x, y ≤ 5 with lines from the origin to the visible points.
Write a program which, given a value for the size, N, computes the number of visible points (x, y) with 0 ≤ x, y ≤ N.

Input

The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a single integer N (1 ≤ N ≤ 1000), which is the size.

Output

For each dataset, there is to be one line of output consisting of: the dataset number starting at 1, a single space, the size, a single space and the number of visible points for that size.

Sample Input

4
2
4
5
231

Sample Output

1 2 5
2 4 13
3 5 21
4 231 32549

题解

我们发现只要这两个坐标最大公约数为1就能看到
每次增加一行和一列，然后递推就可以了

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 4000005
#define mod 51123987
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int n,c;
int dp[1005];
int gcd(int a,int b) {
    return b==0 ? a : gcd(b,a%b);
}
void solve() {
    dp[0]=0;
    siji(i,1,1000) {
    siji(j,0,i) {
        if(gcd(i,j)==1) {
        dp[i]+=2;
        if(i==j) --dp[i];
        }
    }
    dp[i]+=dp[i-1];
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    scanf("%d",&c);
    siji(i,1,c) {
    scanf("%d",&n);
    printf("%d %d %d\n",i,n,dp[n]);
    }
    return 0;
}

Codeforce 527 A. Playing with Paper

One day Vasya was sitting on a not so interesting Maths lesson and making an origami from a rectangular a mm × b mm sheet of paper (a > b). Usually the first step in making an origami is making a square piece of paper from the rectangular sheet by folding the sheet along the bisector of the right angle, and cutting the excess part.
After making a paper ship from the square piece, Vasya looked on the remaining (a - b) mm × b mm strip of paper. He got the idea to use this strip of paper in the same way to make an origami, and then use the remainder (if it exists) and so on. At the moment when he is left with a square piece of paper, he will make the last ship from it and stop.
Can you determine how many ships Vasya will make during the lesson?

Input

The first line of the input contains two integers a, b (1 ≤ b < a ≤ 1012) — the sizes of the original sheet of paper.

Output

Print a single integer — the number of ships that Vasya will make.
Examples

Input

2 1

Output

2

Input

10 7

Output

6

Input

1000000000000 1

Output

1000000000000

Note

Pictures to the first and second sample test.

题解

这道题有点类似gcd
每次ans累加上b/a(b>a)
t=a
a=b%a
b=t
然后这样的复杂度不大只有 $\log n$ 级别

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 4000005
#define mod 51123987
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
ll a,b;
void solve() {
    scanf("%lld%lld",&a,&b);
    if(a>b) swap(a,b);
    ll ans=0;
    while(a!=0) {
    ans+=b/a;
    ll t=a;
    a=b%a;
    b=t;
    }
    printf("%lld\n",ans);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

POJ 2115 C Looooops

Description

A Compiler Mystery: We are given a C-language style for loop of type
for (variable = A; variable != B; variable += C)
statement;
I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2k) modulo 2k.

Input

The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2k) are the parameters of the loop.
The input is finished by a line containing four zeros.

Output

The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.

Sample Input

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

Sample Output

0
2
32766
FOREVER

题解

A+Cx=B(mod 2^k)
这就是一个同余式转换成exgcd的
$Cx+2^ky=B-A$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 5100005
#define MAXM 100005
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
ll A,B,C,k;
ll gcd(ll a,ll b) {
    return b==0 ? a : gcd(b,a%b);
}
void exgcd(ll &x,ll &y,ll a,ll b) {
    if(b==0) {
        x=1;y=0;
        return;
    }
    else {
        exgcd(y,x,b,a%b);
        y-=(a/b)*x;
    }
}
void solve() {
    k=(ll)1<<k;
    ll c=((B-A)%k+k)%k;
    ll g=gcd(C,k);
    ll x,y;
    if(c%g!=0) {
        puts("FOREVER");
    }
    else {
        exgcd(x,y,C,k);
        x=(x%(k/g)+(k/g))%(k/g);
        x=x*(c/g)%(k/g);
        printf("%lld\n",x);
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k)) {
        if(A==0 && B==0 && C==0 && k==0) {
            break;
        }
        solve();
    }
}

449 C. Jzzhu and Apples

Jzzhu has picked n apples from his big apple tree. All the apples are numbered from 1 to n. Now he wants to sell them to an apple store.
Jzzhu will pack his apples into groups and then sell them. Each group must contain two apples, and the greatest common divisor of numbers of the apples in each group must be greater than 1. Of course, each apple can be part of at most one group.
Jzzhu wonders how to get the maximum possible number of groups. Can you help him?

Input

A single integer n (1 ≤ n ≤ 105), the number of the apples.

Output

The first line must contain a single integer m, representing the maximum number of groups he can get. Each of the next m lines must contain two integers — the numbers of apples in the current group.
If there are several optimal answers you can print any of them.

Examples

Input

6

Output

2
6 3
2 4

Input

9

Output

3
9 3
2 4
6 8

Input

2

Output

0

题解

一道数学构造题，我们找出每个大于2小于n/2的质数，然后找出所有没有被用过的它的倍数，如果这些数有偶数个就直接匹配，如果是奇数然后把2×p扔出去
然后剩下的2的倍数两两进行匹配
如果有剩余那么必然是和其他所有的数互质，保证了方案数最大

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int prime[MAXN],tot;
bool isprime[MAXN],used[MAXN];
int tmp[MAXN],h,m;
int ans,outa[MAXN],outb[MAXN];
void solve() {
    scanf("%d",&m);
    memset(isprime,1,sizeof(isprime));
    siji(i,2,100000) {
        if(isprime[i]) {prime[++tot]=i;}
        siji(j,1,tot) {
            if(prime[j]>100000/i) break;
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0) {
                break;
            }
        }
    }
    siji(i,2,tot) {
        if(prime[i]*2>m) break;
        tmp[h=1]=prime[i];
        siji(j,2,100000) {
            if(prime[i]>m/j) break;
            if(!used[j*prime[i]]) {tmp[++h]=j*prime[i];}
        }
        if(h%2==0) {
            siji(j,1,h/2) {
                outa[++ans]=tmp[j*2-1];
                outb[ans]=tmp[j*2];
                used[tmp[j*2-1]]=1;
                used[tmp[j*2]]=1;
            }
        }
        else {
            tmp[2]=prime[i];
            siji(j,1,h/2) {
                outa[++ans]=tmp[j*2];
                outb[ans]=tmp[j*2+1];
                used[tmp[j*2]]=1;
                used[tmp[j*2+1]]=1;
            }
        }
    }
    int last=-1;
    siji(i,2,m) {
        if((!used[i]) && i%2==0) {
            if(last!=-1) {
                outa[++ans]=last;
                outb[ans]=i;
                last=-1;
            }
            else {
                last=i;
            }
        }
    }
    printf("%d\n",ans);
    siji(i,1,ans) {
        printf("%d %d\n",outa[i],outb[i]);
    }
}
int main() {
    solve();
    return 0;
}

POJ 2720 Biorhythms

Description

Some people believe that there are three cycles in a person's life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 28, and 33 days, respectively. There is one peak in each period of a cycle. At the peak of a cycle, a person performs at his or her best in the corresponding field (physical, emotional or mental). For example, if it is the mental curve, thought processes will be sharper and concentration will be easier.
Since the three cycles have different periods, the peaks of the three cycles generally occur at different times. We would like to determine when a triple peak occurs (the peaks of all three cycles occur in the same day) for any person. For each cycle, you will be given the number of days from the beginning of the current year at which one of its peaks (not necessarily the first) occurs. You will also be given a date expressed as the number of days from the beginning of the current year. You task is to determine the number of days from the given date to the next triple peak. The given date is not counted. For example, if the given date is 10 and the next triple peak occurs on day 12, the answer is 2, not 3. If a triple peak occurs on the given date, you should give the number of days to the next occurrence of a triple peak.

Input

You will be given a number of cases. The input for each case consists of one line of four integers p, e, i, and d. The values p, e, and i are the number of days from the beginning of the current year at which the physical, emotional, and intellectual cycles peak, respectively. The value d is the given date and may be smaller than any of p, e, or i. All values are non-negative and at most 365, and you may assume that a triple peak will occur within 21252 days of the given date. The end of input is indicated by a line in which p = e = i = d = -1.

Output

For each test case, print the case number followed by a message indicating the number of days to the next triple peak, in the form:
Case 1: the next triple peak occurs in 1234 days.
Use the plural form ``days'' even if the answer is 1.

Sample Input

0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1

Sample Output

Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.

题解

这道题看到21252就知道是中国剩余定理了
然后注意出现的天数有可能小于给出的date这个时候需要加上21252

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int all,p,e,i,d;
void exgcd(int &x,int &y,int a,int b) {
    if(b==0) {x=1;y=0;}
    else {exgcd(y,x,b,a%b);y-=(a/b)*x;}
}
void solve(int t) {
    all=23*28*33;
    int x,y;
    int ans=0;
    exgcd(x,y,all/23,23);
    x=(x%23+23)%23;
    x=x*p%23;
    ans=(ans+x*(all/23))%all;
    exgcd(x,y,all/28,28);
    x=(x%28+28)%28;
    x=x*e%28;
    ans=(ans+x*(all/28))%all;
    exgcd(x,y,all/33,33);
    x=(x%33+33)%33;
    x=x*i%33;
    ans=(ans+x*(all/33))%all;
    if(ans<=d) ans+=all;
    printf("Case %d: the next triple peak occurs in %d days.\n",t,ans-d);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    int cnt=0;
    while(scanf("%d%d%d%d",&p,&e,&i,&d)!=EOF) {
        if(p==-1) break;
        solve(++cnt);
    }
    return 0;
}

POJ 2720 Last Digits

Description

Exponentiation of one integer by another often produces very large results. In this problem, we will compute a function based on repeated exponentiation, but output only the last n digits of the result. Doing this efficiently requires careful thought about how to avoid computing the full answer.
Given integers b, n, and i, we define the function f(x) recursively by f(x) = bf(x-1) if x > 0, and f(0)=1. Your job is to efficiently compute the last n decimal digits of f(i).

Input

The input consists of a number of test cases. Each test case starts with the integer b (1 <= b <= 100) called the base. On the next line is the integer i (1 <= i <= 100) called the iteration count. And finally, the last line contains the number n (1 <= n <= 7), which is the number of decimal digits to output. The input is terminated when b = 0.

Output

For each test case, print on one line the last n digits of f(i) for the base b specified. If the result has fewer than n digits, pad the result with zeroes on the left so that there are exactly n digits.

Sample Input

2
4
7
10
10
6
3
10
7
0

Sample Output

0065536
000000
4195387

题解

欧拉定理的扩展
$a^x \equiv a^{x \% \varphi (m) + \varphi (m)} \pmod m$
如果a是质数且与m互质，那么定理显然成立
如果a是质数与m不互质
$m=p^r*l$
$(p^r)^{\varphi (l)} \equiv 1 \pmod l$
$(p^r)^{\varphi (l)} = kl+1$
$(p^r)^{\varphi (l)+r} = km+p^r$
$(p^r)^{\varphi (l)+r} = p^r \pmod m$
$\varphi(l) | \varphi (m)$ 所以定理成立

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
int n,b,l;
int pow10[15],f[105][105],ans;
int power(int z,int ex) {
    if(ex==-1) return -1;
    int res=1;
    siji(i,1,ex) {
        res*=z;
        if(res>=pow10[7]) return -1;
    }
    return res;
}
void init() {
    pow10[0]=1;
    siji(i,1,7) pow10[i]=pow10[i-1]*10; 
    siji(j,0,100) f[1][j]=1;
    siji(i,2,100) {
        f[i][0]=1;
        siji(j,1,100) {
            f[i][j]=power(i,f[i][j-1]);
        }
    }
}
ll fpow(ll x,ll c,ll mod) {
    ll res=1,t=x;
    while(c) {
        if(c&1) res=res*t%mod;
        t=t*t%mod;
        c>>=1;
    }
    return res;
}
int euler(int k) {
    int res=k;
    for(int i=2;i<=k/i;++i) {
        if(k%i==0) res=res/i*(i-1);
        while(k%i==0) k/=i;
    }
    if(k>1) res=res/k*(k-1);
    return res;
}
int process(int b,int l,int mod) {
    if(mod==1) return 0;
    if(l==0) return 1;
    if(f[b][l]<0) {
        int eu=euler(mod);
        return fpow(b,process(b,l-1,eu)+eu,mod);
    }
    else {
        return f[b][l]%mod;
    }
}
void solve() {
    if(f[b][l]<0) {
        f[b][l]=process(b,l,pow10[7]);
    }
    ans=f[b][l]%pow10[n];
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    init();
    while(scanf("%d%d%d",&b,&l,&n)!=EOF) {
        if(b==0) break;
        solve();
        gongzi(i,n,1) {
            int k=ans%pow10[i];
            printf("%d",k/pow10[i-1]);
        }
        putchar('\n');
    }
    return 0;
}

POJ 2891 Strange Way to Express Integers

Description

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:
Choose k different positive integers a1, a2, …, ak. For some non-negative m, divide it by every ai (1 ≤ i ≤ k) to find the remainder ri. If a1, a2, …, ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.
“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?

Input

The input contains multiple test cases. Each test cases consists of some lines.
Line 1: Contains the integer k.
Lines 2 ~ k + 1: Each contains a pair of integers ai, ri (1 ≤ i ≤ k).

Output

Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one. If there are no possible values, output -1.

Sample Input

2
8 7
11 9

Sample Output

31

Hint

All integers in the input and the output are non-negative and can be represented by 64-bit integral types.

题解

$m \equiv a \pmod c$
$m \equiv b \pmod d$
$m+cx=a$
$m-dy=b$
$cx+dy=a-b$
$a-=cx$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 4000005
#define mod 51123987
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int k;
ll a[100005],r[100005];
ll all;
ll ab(ll x) {
    if(x<0) x=-x;
    return x;
}
ll gcd(ll a,ll b) {
    return b==0 ? a:gcd(b,a%b);
}
void exgcd(ll &x,ll &y,ll a,ll b) {
    if(b==0) {
    x=1;y=0;
    }
    else {
    exgcd(y,x,b,a%b);
    y-=(a/b)*x;
    }
}
void solve() {
    siji(i,1,k) {
    scanf("%lld%lld",&a[i],&r[i]);
    }
    ll now=a[1],ri=r[1],all=a[1];
    ll x,y;
    siji(i,2,k) {
    ll g=gcd(now,a[i]);
    ll t=ri-r[i];
    if(t%g!=0) {
        puts("-1");
        return;
    }
    exgcd(x,y,now,a[i]);
    x=t/g*x%a[i];
    all=now/g*a[i];
    ri-=now*x%all;
    ri=(ri%all+all)%all;
    now=all;
    }
    printf("%lld\n",ri);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d",&k)!=EOF) {
    solve();
    }
    return 0;
}

BZOJ 1876: [SDOI2009]SuperGCD

Description

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约数）！因此他经常和别人比
赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给Sheng bill岂不是很丢脸！所以你
决定写一个程序来教训他。

Input

共两行：第一行：一个数A。第二行：一个数B。
0 < A , B ≤ 10 ^ 10000。

Output

一行，表示A和B的最大公约数。

Sample Input

12
54

Sample Output

6

题解

这道题我们可以用二进制gcd来简化高精度的运算
假如b==0返回a
假如a和b都是偶数返回2*gcd(a/2,b/2)
假如只有a是偶数返回gcd(a/2,b)
假如只有b是偶数返回gcd(a,b/2)
假如都是奇数返回gcd(a-b,b)
递归调用传的参数空间太大，我们可以用迭代的方式来简化

写跪的原因是减法的退位没退……

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 4000005
#define mod 51123987
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int BASE=100000000;
int WIDTH=8;
struct bignum {
    vector<int> v;
    bignum(long long x=0) {
    *this=x;
    }
    bignum operator =(long long x) {
    v.clear();
    do {
        v.push_back(x%BASE);
        x/=BASE;
    }while(x);
    return *this;
    }
    bignum operator =(const string &str) {
        v.clear();
        int len=(str.length()-1)/WIDTH+1,x;
        xiaosiji(i,0,len) {
            int end=str.length()-i*WIDTH;
            int st=max(0,end-WIDTH);
            sscanf(str.substr(st,end-st).c_str(),"%d",&x);
            v.push_back(x);
        }
        return *this;
    }
    bignum operator /(int num) {
        bignum c;
        c.v.clear();
        int len=v.size();
        siji(i,0,len) c.v.push_back(0);
        --len;
        ll g=0;
        gongzi(i,len,0) {
            ll x=g*BASE+v[i];
            c.v[i]+=x/num;
            g=x%num;
        }
        int s=c.v.size();
        --s;
        gongzi(i,s,1) {
            if(c.v[i]==0) c.v.pop_back();
            else break;
        }
        return c;
    }
    bignum operator *(const bignum &b) {
        bignum c;
        c.v.clear();
        int lena=v.size(),lenb=b.v.size();
        siji(i,0,lena+lenb) c.v.push_back(0);
        xiaosiji(i,0,lena) {
            ll g=0;
            xiaosiji(j,0,lenb) {
                ll x=g+c.v[i+j]+(ll)v[i]*b.v[j];
                c.v[i+j]=x%BASE;
                g=x/BASE;
            }
            int t=lenb+i;
            while(g) {
                ll x=g+c.v[t];
                c.v[t]=x%BASE;
                g=x/BASE;
                ++t;
            }
        }
        int s=c.v.size();
        --s;
        gongzi(i,s,1) {
            if(c.v[i]==0) c.v.pop_back();
            else break;
        }
        return c;
    }
    bignum operator -(const bignum &b) {
        int p=0;
        int g=0,x=0;
        bignum c;
        c.v.clear();
        while(1) {
            x=0;
            if(p<v.size()) x+=v[p];
            if(p<b.v.size()) x-=b.v[p];
            if(p>=v.size() && p>=b.v.size()) break;
            x-=g;
            g=0;
            if(x<0) x+=BASE,g=1;
            c.v.push_back(x);
            ++p;
        }
        return c;
    }
    bool mod2() {
        return v[0]%2==0;
    }
    bool operator < (bignum b) {
    int lena=v.size()-1,lenb=b.v.size()-1;
    if(lena<lenb) return 1;
    else if(lenb<lena) return 0;
    else {
        gongzi(i,lena,0) {
        if(v[i]<b.v[i]) return 1;
        else if(v[i]>b.v[i]) return 0;
        }
    }
    return 0;
    }
    bool operator ==(bignum b) {
        int lena=v.size();
        if(lena!=b.v.size()) return 0;
        siji(i,0,lena-1) {
            if(v[i]!=b.v[i]) return 0;
        }
        return 1;
        }
        bignum operator <=(bignum b) {
        return *this<b || *this == b;
    }
    void out() {
        int s=v.size()-1;
        printf("%d",v[s]);
        --s;
        gongzi(i,s,0) {
            printf("%08d",v[i]);
        }
    }
}a,b;
string stra,strb;
void solve() {
    cin>>stra>>strb;
    a=stra;b=strb;
    bignum z=1;
    while(1) {
        if(a<b) swap(a,b);
        if(b==0) {z=z*a;break;}
        else if(a.mod2() && b.mod2()) {
            z=z*2;
            a=a/2;
            b=b/2;
        }
        else if(a.mod2()) {
            a=a/2;
        }
        else if(b.mod2()) {
            b=b/2;
        }
        else {
            a=a-b;
        }
    }
    z.out();
    putchar('\n');
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

高次不定方程

$A^x \equiv B \pmod C$
如果有解的话x的范围必定在 $[0,C)$
我们不能挨个检查，很慢……但是我们可以使用一种很奇妙的想法
Baby-Step Gaint-Step
类似分块，我们把每m个数算作一块，一共n块，复杂度最优的话是 $m=\sqrt C$
$A^{im-y} \equiv B \pmod C$
如果AC互质那么存在逆元
也就是有
$A^{im} \equiv B×A^{y} \pmod C$
我们把0-m-1的B×A^{y}存在一个hash表里，然后枚举i进行查询，这样复杂度是 $O(\sqrt C)$ 的
如果AC不互质
把式子改成这样的形式
$A^x + kC = B$
我们不断的消去AC之间的最大公约数，如果这个最大公约数不是B的约数那么必然无解
$C_i = C_{i-1} /g$
$B_i = B_{i-1} /g$
$\frac {A^n}{g_1 g_2 g_3...g_n}*A^{x-n} \equiv B_n \pmod C_n$
设 $D=\frac {A^n}{g_1 g_2 g_3...g_n}$
D和C一定互质
然后求出D的逆元乘过去
$A^{x-n} \equiv B_n×D^{-1} \pmod C_n$
然后再求解，最后的答案要加上n

POJ 3243 Clever Y

Description

Little Y finds there is a very interesting formula in mathematics:
$X^Y mod Z = K$
Given X, Y, Z, we all know how to figure out K fast. However, given X, Z, K, could you figure out Y fast?

Input

Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integers X, Z, K (0 ≤ X, Z, K ≤ 109).
Input file ends with 3 zeros separated by spaces.

Output

For each test case output one line. Write "No Solution" (without quotes) if you cannot find a feasible Y (0 ≤ Y < Z). Otherwise output the minimum Y you find.

Sample Input

5 58 33
2 4 3
0 0 0

Sample Output

9
No Solution

题解

这是一道板子题
然而我传参传错了

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
void exgcd(int &x,int &y,int a,int b) {
    if(b==0) {
    x=1;y=0;
    }
    else {
    exgcd(y,x,b,a%b);
    y-=(ll)(a/b)*x;
    }
}
int inv(int a,int b) {
    int x,y;
    exgcd(x,y,a,b);
    return (x%b+b)%b;
}
int gcd(int a,int b) {
    return b==0 ? a : gcd(b,a%b);
}
struct node{
    int next,val;
    int id;
}edge[MOD+5];
int head[MOD+5],sumedge;
void add(int u,int c,int id) {
    edge[++sumedge].next=head[u];
    edge[sumedge].val=c;
    edge[sumedge].id=id;
    head[u]=sumedge;
}
void insert(int x,int id) {
    int u=x%MOD;
    for(int i=head[u];i;i=edge[i].next) {
    if(edge[i].val==x) {
        edge[i].id=id;//这里要更新成较大的id
        return;
    }
    }
    add(x%MOD,x,id);
}
int query(int x) {
    int u=x%MOD;
    for(int i=head[u];i;i=edge[i].next) {
    if(edge[i].val==x) {
        return edge[i].id;
    }
    }
    return -1;
}
int BSGS (int a,int b,int c) {
    int cnt=0,g;
    int d=1;
    while((g=gcd(a,c)) != 1) {
    if(b%g!=0) return -1;
    ++cnt;c/=g;b/=g;
    d=(ll)d*(a/g)%c;
    }
    b=(ll)b*inv(d,c)%c;
    int s=ceil(sqrt((double)c));
    int p=1;
    xiaosiji(i,0,s) {
    if(p==b) return i+cnt;
    insert((ll)p*b%c,i);
    p=(ll)p*a%c;
    }
    int q=p;
    for(int i=s;i-s+1 <= c-1 ; i+=s) {
    int t=query(q);
    if(t!=-1) {
        return i-t+cnt;
    }
    q=(ll)q*p%c;
    }
    return -1;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    int x,z,k;
    while(scanf("%d%d%d",&x,&z,&k)!=EOF) {
    if(x==0 && k==0 && z==0) break;
    memset(head,0,sizeof(head));
    sumedge=0;
    x%=z;k%=z;
    int ans=BSGS(x,k,z);
    if(ans==-1) puts("No Solution");
    else printf("%d\n",ans);
    }
    return 0;
}

原根

$a^r$ 取模一个数 $m$ 周期性是 $\varphi (m)$
由于最小的原根都很小，所以可以暴力求得
求一个质数最小的原根，a是p-1的每个质因子
$g^{\frac{p-1}{a}} \equiv 1 \pmod p$
那么g就不合法

POJ 1284 Primitive Roots

Description

We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and only if the set { (xi mod p) | 1 <= i <= p-1 } is equal to { 1, ..., p-1 }. For example, the consecutive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a primitive root modulo 7.
Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p.

Input

Each line of the input contains an odd prime numbers p. Input is terminated by the end-of-file seperator.

Output

For each p, print a single number that gives the number of primitive roots in a single line.

Sample Input

23
31
79

Sample Output

10
8
24

题解

一个数原根的个数是
$\varphi(\varphi (p))$
这道题的答案就是
$\varphi (p-1)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
void solve(int p){
    int t=p-1;
    int eu=t;
    for(int i=2;i<=t/i;++i) {
    if(t%i==0) {
        eu=eu/i*(i-1);
        while(t%i==0) t/=i;
    }
    }
    if(t>1) eu=eu/t*(t-1);
    printf("%d\n",eu);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    int p;
    while(scanf("%d",&p)!=EOF) {
    solve(p);
    }
    return 0;
}

BZOJ 2242: [SDOI2011]计算器

Description

你被要求设计一个计算器完成以下三项任务：
1、给定y,z,p,计算Y^Z Mod P 的值；
2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；
3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

Input

输入包含多组数据。
第一行包含两个正整数T,K分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。
以下行每行包含三个正整数y,z,p，描述一个询问。

Output

对于每个询问，输出一行答案。对于询问类型2和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”，注意逗号与“I”之间有一个空格。

Sample Input

【样例输入1】

3 1
2 1 3
2 2 3
2 3 3

【样例输入2】

3 2
2 1 3
2 2 3
2 3 3

【数据规模和约定】

对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。

Sample Output

【样例输出1】

2
1
2

【样例输出2】

2
1
0

题解

我觉得p是质数是骗人的，因为第二问是exgcd
因为没初始化哈希表WA了
第一问快速幂
第二问扩展gcd
第三问BSGS

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int T,k;
ll fpow(ll x,ll c,ll p) {
    ll t=x,res=1;
    while(c) {
    if(c&1) res=res*t%p;
    t=t*t%p;
    c>>=1;
    }
    return res;
}
void solve1(ll y,ll z,ll p) {
    ll ans=fpow(y,z,p);
    printf("%lld\n",ans);
}
ll exgcd(ll &x,ll &y,ll a,ll b) {
    if(b==0) {
    x=1;y=0;
    return a;
    }
    else {
    ll res=exgcd(y,x,b,a%b);
    y-=(a/b)*x;
    return res;
    }
}
ll gcd(ll a,ll b) {
    return b == 0 ? a : gcd(b,a%b);
}
ll inv(ll a,ll b) {
    ll x,y;
    exgcd(x,y,a,b);
    return (x%b+b)%b;
}
void solve2(ll y,ll k,ll p) {
    ll l,z;
    ll g=exgcd(l,z,y,p);
    l=(l%(p/g)+(p/g))%(p/g);
    if(k%g!=0) {
    puts("Orz, I cannot find x!");
    }
    else {
    l=l*(k/g)%(p/g);
    printf("%lld\n",l);
    }
}
struct node {
    int next,val,id;
}edge[MOD+5];
int head[MOD+5],sumedge;
void add(int u,int c,int id) {
    edge[++sumedge].next=head[u];
    edge[sumedge].val=c;
    edge[sumedge].id=id;
    head[u]=sumedge;
}
void insert(int x,int id) {
    int u=x%MOD;
    for(int i=head[u];i;i=edge[i].next) {
    if(edge[i].val==x) {
        edge[i].id=id;
        return;
    }
    }
    add(u,x,id);
}
int query(int x) {
    int u=x%MOD;
    for(int i=head[u];i;i=edge[i].next) {
    if(edge[i].val==x) {
        return edge[i].id;
    }
    }
    return -1;
}
void solve3(ll a,ll b,ll c) {
    memset(head,0,sizeof(head));
    sumedge=0;
    int cnt=0;
    ll g,d=1;
    a%=c;b%=c;
    while((g=gcd(a,c))!=1) {
    if(b%g!=0) {
        puts("Orz, I cannot find x!");
        return;
    }
    b/=g;c/=g;++cnt;
    d=d*(a/g)%c;
    }
    b=b*inv(d,c)%c;
    int s=sqrt(c);
    ll p=1;
    for(int i=0;i<s;++i) {
    if(p==b) {
        printf("%d\n",i+cnt);
        return;
    }
    insert(p*b%c,i);
    p=p*a%c;
    }
    ll q=p;
    for(int i=s;i-s+1<=c-1;i+=s) {
    int t=query(q);
    if(t!=-1) {
        printf("%d\n",i-t+cnt);
        return;
    }
    q=q*p%c;
    }
    puts("Orz, I cannot find x!");
}
void trans() {
    scanf("%d%d",&T,&k);
    ll y,z,p;
    siji(i,1,T) {
    scanf("%lld%lld%lld",&y,&z,&p);
    if(k==1) {
        solve1(y,z,p);
    }
    else if(k==2) {
        solve2(y,z,p);
    }
    else {
        solve3(y,z,p);
    }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    trans();
    return 0;
}

HDU 3930 Broot

Problem Description

There is a way of encryption in the Digital planet. If the number x, who lives in M area, K layer, then it will change its name to x ^ K mod M, that is newx = x ^ k mod m. Now the Digital Kingdom wants to make a program, which can find all the original number of a name living in some area, some layer. If there is no solution, output -1.

Input

There are multiply test cases. Each test case contains there integers k, m , newx ,(0 <= newx , m ,k <= 1.5*10^15) , m is a prime number.

Output

For each test case, you should output some lines, the format of the first line is: “caseN:” (N is the label of test case). Then next lines each contain a number x, output x as ascending order. (0 <= x < m)

Sample Input

1 5 4
2 13 8
3 13 8

Sample Output

case1:
4
case2:
-1
case3:
2
5
6

题解

这道题教会我如何解一个超越方程（误）
$x^k = newx \pmod m$
我们考虑一个m的原根root
肯定能找到一个
$root^l \equiv newx \pmod m$
而我们循环的周期是m-1
那么就有
$root^{l+(m-1)y} \equiv newx \pmod m$
$l+(m-1)y \equiv 0 \pmod k$
相当于
$kx+(m-1)y=l$
然后求出x的所有解
范围在(0,m-1]
但是这个时候两个long long相乘会爆，我们需要用加法代替乘法

题解

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
ll multi(ll a,ll b,ll mod) {
    ll t=a,res=0;
    b%=mod;a%=mod;
    while(b) {
    if(b&1) res=(res+t)%mod;
    t=(t+t)%mod;
    b>>=1;
    }
    return res;
}
void exgcd(ll &x,ll &y,ll a,ll b) {
    if(b==0) {
    x=1;y=0;
    }
    else {
    exgcd(y,x,b,a%b);
    y-=(a/b)*x;
    }
}
ll gcd(ll a,ll b) {
    return b == 0 ? a : gcd(b,a%b);
}
ll inv(ll a,ll b) {
    ll x,y;
    exgcd(x,y,a,b);
    return (x%b+b)%b;
}
struct node {
    int next,id;
    ll val;
}edge[1000005];
int head[MOD+5],sumedge;
void add(int u,ll c,int id) {
    edge[++sumedge].next=head[u];
    edge[sumedge].val=c;
    edge[sumedge].id=id;
    head[u]=sumedge;
}
void insert(ll x,int id) {
    int u=x%MOD;
    for(int i=head[u];i;i=edge[i].next) {
    if(edge[i].val==x) {
        edge[i].id=id;
        return;
    }
    }
    add(u,x,id);
}
ll query(ll x) {
    int u=x%MOD;
    for(int i=head[u];i;i=edge[i].next) {
    if(edge[i].val==x) {
        return edge[i].id;
    }
    }
    return -1;
}
ll BSGS(ll a,ll b,ll c) {
    memset(head,0,sizeof(head));
    sumedge=0;
    int cnt=0;
    ll g,d=1;
    a%=c;b%=c;
    while((g=gcd(a,c))!=1) {
    if(b%g!=0) {
        return -1;
    }
    b/=g;c/=g;++cnt;
    d=multi(d,a/g,c);
    }
    b=multi(b,inv(d,c),c);
    int s=sqrt(c);
    ll p=1;
    for(int i=0;i<s;++i) {
    if(p==b) {
        return i+cnt;
    }
    insert(multi(p,b,c),i);
    p=multi(p,a,c);
    }
    ll q=p;
    for(int i=s;i-s+1<=c-1;i+=s) {
    int t=query(q);
    if(t!=-1) {
        return i-t+cnt;
    }
    q=multi(p,q,c);
    }
    return -1;
}
ll fpow(ll x,ll c,ll mod) {
    ll t=x,res=1;
    while(c) {
    if(c&1) res=multi(res,t,mod);
    t=multi(t,t,mod);
    c>>=1;
    }
    return res;
}
ll prime[105],tot;
ll primitive_root(ll p) {
    tot=0;
    ll t=p-1;
    for(int i=2;i<=t/i;++i) {
    if(t%i==0) {
        prime[++tot]=i;
        while(t%i==0) t/=i;
    }
    }
    if(t>1) prime[++tot]=t;
    t=p-1;
    siji(i,2,t) {
    siji(j,1,tot) {
        if(fpow(i,t/prime[j],p)==1) {
        goto fail;
        }
    }
    return i;
        fail:;
    }
}
vector<ll> v;
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    ll k,m,newx;
    int cnt=0;
    while(scanf("%lld%lld%lld",&k,&m,&newx)!=EOF) {
    v.clear();
    ++cnt;
    printf("case%d:\n",cnt);
    ll r=primitive_root(m);
    ll l=BSGS(r,newx,m);
    if(l==-1) {
        puts("-1");
        continue;
    }
    ll x,y,g;
    g=gcd(k,m-1);
    if(l%g) {
        puts("-1");
        continue;
    }
    l/=g;k/=g;
    ll t=(m-1)/g;
    exgcd(x,y,k,t);
    x=(x%t+t)%t;
    x=multi(x,l,t);
    while(x<=(m-1)) {
        ll ans=fpow(r,x,m);
        v.push_back(ans);
        x+=t;
    }
    sort(v.begin(),v.end());
    int s=v.size();
    xiaosiji(i,0,s) {
        printf("%lld\n",v[i]);
    }
    }
    return 0;
}

HDU 3223 Decrypt Messages

Problem Description

In the game BioHazard 4, the president's daughter has been abducted by some crazy villagers. Leon S. Kennedy, the secret agent of White House, goes to rescue her. He keeps in contact with Hunnigan, the president's secretary.
But the time in their contact log has been encrypted, using the following method:
Count the number of seconds from 2000.01.01 00:00:00 to that time, assume this number is x. Then calculate xq, modulo it by a prime number p. The remainder a is the encrypted number.
Your task is to help Leon write a program to decrypt the contact log, and tell him all the possible original time.
1. Remember that if the year can be divided evenly by 4 but can't be divided evenly by 100, or it can be divided evenly by 400, this year is a leap year. The February of a leap year has 29 days, while the February of other years has 28 days.
2. In this problem, if the year modulo 10 is 5 or 8, at the end of this year, there is one “leap second”, i.e., the second after 2005.12.31 23:59:59 is 2005.12.31 23:59:60, and after that second, it's 2006.01.01 00:00:00.
You may assume that from 2000.01.01 00:00:00 till that time, less than p seconds have passed.

Input

There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the test cases.
For each test case, a single line of three integers: p, q, and a. (2

Output

The time. If there are multiple solutions, you must output all possible solutions in chronological order.
If the solution doesn't exist, output Transmission error instead.
See the sample output for further details.

Sample Input

2
3 2 1
3 2 2

Sample Output

Case #1:
2000.01.01 00:00:01
2000.01.01 00:00:02
Case #2:
Transmission error

题解

这个就是上面的板子加上时间转换
要注意a==0的情况，这个时候方程只有一个解就是x=0

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
//#define ivorysi
using namespace std;
typedef long long ll;
const ll second =1;
const ll minute = 60;
const ll hour = 3600;
const ll day = hour*24;
ll m(int d) {return (ll)d*day;}
const ll Lyear = 366*day;
const ll Uyear = 365*day;
//          1      3    5      7  8    10    12 
int mo[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; 
ll multi(ll a,ll b,ll mod) {
    ll t=a,res=0;
    b%=mod;a%=mod;
    while(b) {
        if(b&1) res=(res+t)%mod;
        t=(t+t)%mod;
        b>>=1;
    }
    return res;
}
void exgcd(ll &x,ll &y,ll a,ll b) {
    if(b==0) {
        x=1;y=0;
    }
    else {
        exgcd(y,x,b,a%b);
        y-=(a/b)*x;
    }
}
ll gcd(ll a,ll b) {
    return b == 0 ? a : gcd(b,a%b);
}
ll inv(ll a,ll b) {
    ll x,y;
    exgcd(x,y,a,b);
    return (x%b+b)%b;
}
struct node {
    int next,id;
    ll val;
}edge[1000005];
int head[MOD+5],sumedge;
void add(int u,ll c,int id) {
    edge[++sumedge].next=head[u];
    edge[sumedge].val=c;
    edge[sumedge].id=id;
    head[u]=sumedge;
}
void insert(ll x,int id) {
    int u=x%MOD;
    for(int i=head[u];i;i=edge[i].next) {
        if(edge[i].val==x) {
            edge[i].id=id;
            return;
        }
    }
    add(u,x,id);
}
ll query(ll x) {
    int u=x%MOD;
    for(int i=head[u];i;i=edge[i].next) {
        if(edge[i].val==x) {
            return edge[i].id;
        }
    }
    return -1;
}
ll BSGS(ll a,ll b,ll c) {
    memset(head,0,sizeof(head));
    sumedge=0;
    int cnt=0;
    ll g,d=1;
    a%=c;b%=c;
    while((g=gcd(a,c))!=1) {
        if(b%g!=0) {
            return -1;
        }
        b/=g;c/=g;++cnt;
        d=multi(d,a/g,c);
    }
    b=multi(b,inv(d,c),c);
    int s=sqrt(c);
    ll p=1;
    for(int i=0;i<s;++i) {
        if(p==b) {
            return i+cnt;
        }
        insert(multi(p,b,c),i);
        p=multi(p,a,c);
    }
    ll q=p;
    for(int i=s;i-s+1<=c-1;i+=s) {
        int t=query(q);
        if(t!=-1) {
            return i-t+cnt;
        }
        q=multi(p,q,c);
    }
    return -1;
}
ll fpow(ll x,ll c,ll mod) {
    ll t=x,res=1;
    while(c) {
        if(c&1) res=multi(res,t,mod);
        t=multi(t,t,mod);
        c>>=1;
    }
    return res;
}
ll prime[105],tot;
ll primitive_root(ll p) {
    tot=0;
    ll t=p-1;
    for(int i=2;i<=t/i;++i) {
        if(t%i==0) {
            prime[++tot]=i;
            while(t%i==0) t/=i;
        }
    }
    if(t>1) prime[++tot]=t;
    t=p-1;
    siji(i,2,t) {
        siji(j,1,tot) {
            if(fpow(i,t/prime[j],p)==1) {
                goto fail;
            }
        }
        return i;
        fail:;
    }
}
bool is_yleap(ll x) {
    return (x%4==0 && x%100!=0) || x%400==0;
}
bool is_sleap(ll x) {
    return x%10==5 || x%10==8;
}
void trans(ll x) {
    ll yy=2000,mm=1,dd=1,hh=0,mi=0,se=0;
    while(x) {
        ll yt=0;
        if(is_yleap(yy)) {yt=Lyear;mo[2]=29;}
        else {yt=Uyear;mo[2]=28;}
        if(is_sleap(yy)) yt++;
        if(x>=yt) {
            ++yy;x-=yt;continue;
        }
        while(x) {
            ll mt=0;
            mt=m(mo[mm]);
            if(mm==12 && is_sleap(yy)) ++mt;
            if(x>=mt) {
                ++mm;x-=mt;continue;
            }
            while(x) {
                ll dt=day;
                if(is_sleap(yy) && mm==12 && dd==31) ++dt;
                if(x>=dt) {
                    ++dd;x-=dt;continue;
                }
                if(x) {hh+=x/hour;x%=hour;}
                if(x) {mi+=x/minute;x%=minute;}
                if(x) {se+=x/second;x%=second;}
            }
        }
    }
    if(hh==24) {
        hh=23;mi=59;se=60;
    }
    printf("%4lld.%02lld.%02lld %02lld:%02lld:%02lld\n"
        ,yy,mm,dd,hh,mi,se);
}
vector<ll> v;
int T;
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    ll k,m,newx;
    scanf("%d",&T);
    siji(i,1,T) {
        scanf("%lld%lld%lld",&m,&k,&newx);
        v.clear();
        printf("Case #%d:\n",i);
        ll r=primitive_root(m);
        if(newx==0) {
            puts("2000.01.01 00:00:00");
            continue;
        }
        ll l=BSGS(r,newx,m);
        if(l==0) l=m-1;
        if(l==-1) {
            puts("Transmission error");
            continue;
        }
        ll x,y,g;
        g=gcd(k,m-1);
        if(l%g) {
            puts("Transmission error");
            continue;
        }
        l/=g;k/=g;
        ll t=(m-1)/g;
        exgcd(x,y,k,t);
        x=(x%t+t)%t;
        x=multi(x,l,t);
        if(x==0) x=t;
        while(x<=(m-1)) {
            ll ans=fpow(r,x,m);
            v.push_back(ans);
            x+=t;
        }
        sort(v.begin(),v.end());
        int s=v.size();
        xiaosiji(i,0,s) {
            trans(v[i]);
        }
    }
    return 0;
}