题解 P4028 【New Product】

NaCly_Fish · 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;
}