QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#420567 | #8706. 解方程 | Williamxzh | 0 | 0ms | 0kb | C++23 | 1.4kb | 2024-05-24 20:12:19 | 2024-05-24 20:12:24 |
answer
#include <bits/stdc++.h>
#define il inline
#define B __int128
using namespace std;
il B read(){
B x=0,c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-48,c=getchar();
return x;
}
void write(B x){
if(x>9) write(x/10);
putchar(x%10+48);
}
il void print(B x,char c){write(x),putchar(c);}
il B qp(B a,B b,B mod){
B ans=B(1);
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod,b>>=1;
}
return ans;
}
const int N=10;const B inf=1e6;
int T,n,ck;B p,m,a[N],b[N],c[N],cur[N],iv[N],ans;
B x,y,z,u,v,w,s,t;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);p=read(),m=B(sqrtl(p)),ans=0;
for(int i=1;i<=n;++i) a[i]=read(),b[i]=read(),c[i]=read(),iv[i]=qp(a[i]+1,p,p-2);
for(B i=min(inf,m);i;--i){
ck=1;for(int j=1;j<=n;++j) cur[j]=(c[j]-a[j]*i%p*i%p+p)*iv[j]%p;
for(int j=1;j<n;++j) if(cur[j]!=cur[j+1]){ck=0;break;}
if(ck && i*i+cur[1]<p){ans=i*i+cur[1];break;}
ck=1;for(int j=1;j<=n;++j) cur[j]=(c[j]-a[j]*i%p*i%p-a[i]*i%p+B(2)*p)*iv[i]%p;
for(int j=1;j<n;++j) if(cur[j]!=cur[j+1]){ck=0;break;}
if(ck && i*i+cur[1]+i<p){ans=i*i+cur[1]+i;break;}
ck=1;x=i*i+B(2)*i;
for(int j=1;j<=n;++j) if((a[i]*x%p)!=c[i]){ck=0;break;}
if(ck && i*i+i*2<p){ans=i*i+cur[1]+i;break;}
}
print(ans,'\n');
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
40 5 923097614961380909 400075690252081333 1 336925156808111277 125871709464257940 1 69865713802049054 625686524906165721 1 231604442249496820 240111021937539825 1 466914943115931347 877342215923645363 1 405475742085577903 5 954878053655579819 314356765890269968 1 479476497512555507 3066762309305691...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #2:
score: 0
Runtime Error
input:
40 5 923097614961380909 400075690252081333 1 36226200850654830 125871709464257940 1 801294848271831 625686524906165721 1 167289389520696370 240111021937539825 1 566782367688890103 877342215923645363 1 437769344508562455 5 954878053655579819 314356765890269968 1 481049707495526324 306676230930569168 ...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #3:
score: 0
Runtime Error
input:
40 5 923097614961380909 400075690252081333 1 167001433276774274 125871709464257940 1 775646046137144068 625686524906165721 1 792747143363812162 240111021937539825 1 511005265275196004 877342215923645363 1 898824348527556482 5 954878053655579819 314356765890269968 1 501561843363742850 306676230930569...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #4:
score: 0
Runtime Error
input:
40 5 923097614961380909 400075690252081333 1 711217741985470914 125871709464257940 1 444725029628910905 625686524906165721 1 74716258575747726 240111021937539825 1 409246477245810521 877342215923645363 1 369189987866325821 5 954878053655579819 314356765890269968 1 80576853778385871 30667623093056916...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #5:
score: 0
Runtime Error
input:
40 5 923097614961380909 400075690252081333 6 711217743785736202 125871709464257940 6 444725031004785657 625686524906165721 3 74716259410497736 240111021937539825 9 409246477844369931 877342215923645363 10 369189993610199341 5 954878053655579819 314356765890269968 5 80576853778385871 3066762309305691...
output:
result:
Subtask #6:
score: 0
Runtime Error
Test #6:
score: 0
Runtime Error
input:
40 5 923097614961380909 400075690252081333 95 711217768089317590 125871709464257940 95 444725049579094809 625686524906165721 98 74716266923247826 240111021937539825 92 409246509568018661 877342215923645363 91 369190035253282361 5 954878053655579819 314356765890269968 96 80576904711097456 30667623093...