QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420592#8706. 解方程Williamxzh15 1796ms3980kbC++232.3kb2024-05-24 20:29:482024-05-24 20:29:49

Judging History

你现在查看的是最新测评结果

  • [2024-05-24 20:29:49]
  • 评测
  • 测评结果:15
  • 用时:1796ms
  • 内存:3980kb
  • [2024-05-24 20:29:48]
  • 提交

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-2,p);
        for(B i=min(inf,m);i;--i){
            ck=1;for(int j=1;j<=1;++j) cur[j]=(c[j]-a[j]*i%p*i%p+p)%p*iv[j]%p;
            //for(int j=1;j<=n;++j) if((a[j]*(i*i+cur[j])%p+cur[j])%p!=c[j]) puts("*");
            if(cur[1]<i){
                x=y=cur[1];
                for(int j=2;j<=n;++j){
                    y=(x*y)%i;
                    if(((a[j]*(i*i+x)%p+y)%p)!=c[j]){ck=0;break;}
                }
                if(ck && i*i+cur[1]<p){ans=i*i+cur[1];break;}
            }
            ck=1;for(int j=1;j<=1;++j) cur[j]=(c[j]-a[j]*i%p*(i+1)%p+p)%p*iv[j]%p;
            if(cur[1]<i){
                x=y=cur[1];
                for(int j=2;j<=n;++j){
                    y=(x*y)%i;
                    if(((a[j]*(i*i+x+i)%p+y)%p)!=c[j]){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[j]*x%p)!=c[j]){ck=0;break;}
            if(ck && i*i+i*2<p){ans=i*i+2*i;break;}
        }
        print(ans,'\n');
    }
    return 0;
}
/*
1
5 923097614961380909
400075690252081333 1 336925156808111277
125871709464257940 1 69865713802049054
625686524906165721 1 231604442249496820
240111021937539825 1 466914943115931347
877342215923645363 1 405475742085577903

1
5 954878053655579819
314356765890269968 1 479476497512555507
306676230930569168 1 766951581918930183
431060589896613060 1 490177297768163598
225430116740155909 1 393506569589398587
104392359369916055 1 797573285247883669
*/

详细

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 421ms
memory: 3840kb

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:

105920391906
517298493095
67193831219
454985828211
684359412322
641300692901
843969628814
441618717944
969809963928
839021293810
844536308194
864204489953
5716199622
878033311810
235677761660
860055517480
657591767649
831659873919
212006513628
404950041144
707100669788
697228408265
379537727517
1651...

result:

ok 40 lines

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 1729ms
memory: 3720kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
831659873919
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 1st lines differ - expected: '78105920391906', found: '0'

Subtask #3:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 1280ms
memory: 3708kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 1st lines differ - expected: '2678105920391906', found: '0'

Subtask #4:

score: 0
Wrong Answer

Test #4:

score: 0
Wrong Answer
time: 1796ms
memory: 3980kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 1st lines differ - expected: '879580490959010998', found: '0'

Subtask #5:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 1277ms
memory: 3604kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 1st lines differ - expected: '879580490959010998', found: '0'

Subtask #6:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 1770ms
memory: 3980kb

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...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 1st lines differ - expected: '879580490959010998', found: '0'