自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 21:55:43，当前版本为作者最后更新于2019-01-30 20:45:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

暴力出奇迹！！

我是一个蒟蒻，我非常喜欢暴力算法，然后我就用暴力过了这道题。。
枚举答案$\text{ans}$，从$1$~$p-1$，检查是否满足答案，如果满足就输出；如果枚举完了还没得出答案，输出无解就行了。。

正确性证明也很简单，根据费马小定理，对于$a^n$模质数$p$的循环节长度为$p-1$(或者说是$φ(p)$)，所以$\text{ans}$肯定不会比这个大，于是这道题就做完了。。

代码：
其实不加循环展开和$\text{O}_3$也能过

#pragma GCC optimize (3)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 50003
#define ll long long
#define reg register
using namespace std;

bool vis[N];
int a,b,p,ans,cur;

inline void read(int &x){
	x = 0;
	char c = getchar();
	while(c<'0'||c>'9') c = getchar();
	while(c>='0'&&c<='9'){
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
}

void print(int x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

inline void println(string str){
	int l = str.length();
	for(reg int i=0;i<l;++i) putchar(str[i]);
	putchar('\n');
}

void solve(){
	cur = 1;
	read(p),read(a),read(b);
	for(reg int i=0;;++i){
		if(cur==b){
			ans = i;
			break;
		}
		if(i>p){
			println("Couldn't Produce!");
			return;
		}
		cur = (ll)cur*a%p;
	}
	print(ans);
	putchar('\n');
}

int main(){
	reg int T,t;
	read(T);
	t = (T>>4)<<4;
	T &= 15;
	while(t){
		solve(),solve(),solve(),solve();
		solve(),solve(),solve(),solve();
		solve(),solve(),solve(),solve();
		solve(),solve(),solve(),solve();
		t -= 16;
	}
	while(T--) solve();
	return 0;
}