結果

問題 No.551 夏休みの思い出（２）
ユーザー dontwannacry
提出日時 2025-04-25 22:34:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,706 ms / 4,000 ms
コード長 1,564 bytes
コンパイル時間 2,188 ms
コンパイル使用メモリ 202,948 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2025-04-25 22:35:22
合計ジャッジ時間 23,910 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int P,R,A,B,C,val[10010],base,lim,ans[10],len;
unordered_map<int,int>M;
int Pow(int A,int B,const int P){
	int res = 1;
	while(B){
		if(B&1){res = 1ll*A*res%P;}
		A = 1ll*A*A%P;
		B >>= 1;
	}
	return res;
}
void solve(const int P){
	cin >> A >> B >> C;len = 0;
	int sq = ((1ll*B*B-4ll*A*C)%P+P)%P,tmp = sq,nowti = -1;
	if(sq == 0){
		int PL12 = 1ll*(P-B)%P*Pow(2*A,P-2,P)%P;
		cout << PL12 << "\n";
		return;
	}
	sq = Pow(val[1],P-2,P);
	for(int i = 0;i <= lim;++i){
		if(M.find(tmp) != M.end()){
			nowti = i*base+M[tmp];
			break;
		}
		tmp = 1ll*tmp*sq%P;
	}
	if(nowti == -1||(nowti&1)){cout << "-1\n";return;}
	int Mig = nowti/2,Yak = ((nowti+P-1)/2)%(P-1),JF17 = Pow(2*A,P-2,P);
	Mig = Pow(R,Mig,P);Yak = Pow(R,Yak,P);
	ans[++len] = 1ll*(Mig-B+P)*JF17%P;
	ans[++len] = (1ll*(-Mig-B+P)*JF17%P+P)%P;
	ans[++len] = 1ll*(Yak-B+P)*JF17%P;
	ans[++len] = (1ll*(-Yak-B+P)*JF17%P+P)%P;
	sort(ans+1,ans+1+len);len = unique(ans+1,ans+1+len)-ans-1;
	for(int i = 1;i <= len;++i){cout << ans[i] << " ";}cout << "\n";
}
void init(const int P){
	lim = 100000;
	int ti = 0,va = 1;val[0] = 1;
	while(ti <= lim&&ti <= P){
		val[1] = va;M[va] = base = ti;
		++ti;va = 1ll*va*R%P;
	}
	lim = P/lim+1;
	for(int i = 2;i <= lim;++i){val[i] = 1ll*val[i-1]*val[1]%P;}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("equation.in","r",stdin);
    // freopen("equation.out","w",stdout);
	cin >> P >> R;init(P);
    int T = 1;cin >> T;
	for(int i = 1;i <= T;++i){solve(P);}
	return 0;
}
0