## 【51NOD 1135】原根

### 解题报告

wiki上给出了这样一个上界：$O(n^{0.499})$，但$n$要大于$e^{e^{24}}$，所以对于OI题没什么用QwQ

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Get_Primitive_Root(int w) {
vector<int> pri;
for (int i=2,lim=ceil(sqrt(w)),cur=w-1;i<lim;i++) {
if (cur % i == 0) {
pri.push_back(i);
while (cur % i == 0)
cur /= i;
}
if (cur > 1 && i == lim - 1)
pri.push_back(cur);
}
static auto Pow = [](int w, int t, int MOD) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t & 1) ret = (LL)ret * w % MOD;
return ret;
};
if (!pri.size()) return 2;
for (int i=2;i<=w;i++) {
for (int j=pri.size()-1;~j;j--) {
if (Pow(i,w/pri[j],w) == 1) break;
if (!j) return i;
}
}
}

int main() {
return 0;
}


## 【POJ 2891】Strange Way to Express Integers

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

char c=getchar(); LL ret=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

LL GCD(LL a,LL b){return b?GCD(b,a%b):a;}

LL EX_GCD(LL a, LL b, LL &x, LL &y){
if (!b) {x=1;y=0;}
else {EX_GCD(b,a%b,y,x);y-=a/b*x;}
}

inline LL EX_GCD(LL a, LL b, LL pur){
LL ret,tmp; EX_GCD(a,b,ret,tmp);
return ((ret*pur)%b + b) % b;
}

int main(){
int n; while (~scanf("%d",&n)) {
for (int i=1;i<n;i++) {
b2 = read(); a2 = read(); gcd = GCD(b1,b2);
if (!tag) {
if ((a2-a1)%gcd) tag = 1, printf("-1\n");
else {
A = EX_GCD(b1/gcd,b2/gcd,(a2-a1)/gcd);
a1 = a1 + (A*b1);
b1 = b1/gcd*b2; a1 %= b1;
}
}
}
if (!tag) printf("%lld\n",((a1%b1)+b1)%b1);
}
return 0;
}


## 【POJ 1006】Biorhythms

#include<iostream>
#include<cstdio>
using namespace std;

const int SGZ = 3;
const int MAXN = 5;
const int SUM = 23*28*33;

int T,arr[]={0,28*33,23*33,23*28},ori[]={0,23,28,33},a[MAXN],d;

void EX_GCD(int a, int b, int &x, int &y){
if (!b) x=1, y=0;
else EX_GCD(b,a%b,y,x), y -= a/b*x;
}

inline int rev(int w, int MOD){
int ret,tmp; EX_GCD(w,MOD,ret,tmp);
return ret;
}

int main(){
while (cin>>a[1]>>a[2]>>a[3]>>d && a[1] != -1) {
int vout = 0;
for (int i=1;i<=SGZ;i++) vout += a[i]*rev(arr[i],ori[i])*arr[i];
vout = ((vout-d)%SUM+SUM)%SUM; vout = vout?vout:SUM;
printf("Case %d: the next triple peak occurs in %d days.\n",++T,vout);
}
return 0;
}