【51NOD 1135】原根

相关链接

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135
神犇题解Ⅰ:http://blog.csdn.net/u013486414/article/details/47781857
神犇题解Ⅱ:http://littleclown.github.io/2016/05/16/Study-Math-Mod-Root/

解题报告

就是一个求原根的模板题
相关的证明在这里:http://blog.csdn.net/zhang20072844/article/details/11541133

值得注意的是,验证原根现在可以做到$O(logn)$了
不过找原根的复杂度似乎没有比较紧的上界?
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() {
    printf("%d\n",Get_Primitive_Root(read())); 
    return 0;
}

【POJ 2891】Strange Way to Express Integers

题目传送门:http://poj.org/problem?id=2891

这个东西,不保证互质,所以中国剩余定理上不了
于是就得合并方程:
把\(\left\{ \begin{array}{l}
x \equiv {a_1}(Mod{\rm{ }}{b_1})\\
x \equiv {a_2}(Mod{\rm{ }}{b_2})
\end{array} \right.\)
替换成\(x \equiv {a_1} + A \cdot {b_1}(Mod{\rm{ }}\frac{{{b_1} \cdot {b_2}}}{{GCD({b_1},{b_2})}})\)
其中A为\(A \cdot {b_1} – B \cdot {b_2} = {a_2} – {a_1}\)的最小非负整数解
至于推导过程嘛,就自己推一推咯,不想写latex了,太费时间

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

inline LL read(){
	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)) {
		LL b1=read(),a1=read(),a2,b2,tag=0,A,tmp,gcd;
		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;
} 

另外,这个题,貌似会爆long long,不过只要你的代码跟我的差不多,就能过QAQ
不得不说,这个题目真的是出得辣鸡,数据范围都没给全………

【POJ 1006】Biorhythms

题目传送门:http://poj.org/problem?id=1006
中文版题目:http://hzwer.com/3299.html

完全看不懂题,不过既然大家都说是模线性方程组,那就按照那样做咯!
中国剩余定理的话,看看wiki就明白啦:https://en.wikipedia.org/wiki/Chinese_remainder_theorem

#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;
}