QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #577364 | #1835. Fancy Formulas | World_Creater | WA | 80ms | 3628kb | C++17 | 691b | 2024-09-20 10:46:33 | 2024-09-20 10:46:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int qpow(int a,int b,int mod)
{
if(b==0) return 1;
int g=qpow(a,b/2,mod);
g=1ll*g*g%mod;
if(b&1) g=1ll*g*a%mod;
return g;
}
int p,q;
typedef long long ll;
int main()
{
cin>>p>>q;
while(q--)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if((a+b)%p!=(c+d)%p)
{
cout<<"-1\n";
continue ;
}
int s=qpow((a+b)%p,p-2,p);
a=1ll*a*s%p;
c=1ll*c*s%p;
int ans=0;
for(;;ans++)
{
ll wl=(a*1ll<<ans)-(1ll<<ans)+1,wr=a*1ll<<ans;
if(wr/p==wl/p)
{
wl%=p,wr%=p;
if(c>=wl&&c<=wr) break ;
}
else
{
wl%=p,wr%=p;
if(c>=wl||c<=wr) break ;
}
}
cout<<ans<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
5 10 2 1 3 0 2 1 4 4 1 3 4 0 0 2 0 4 3 3 1 2 0 1 0 1 0 3 0 3 0 1 0 1 1 2 4 4 1 0 1 1
output:
2 1 2 -1 -1 0 0 0 1 -1
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 80ms
memory: 3628kb
input:
97 100000 30 56 74 12 95 39 8 29 11 42 76 74 48 63 58 53 74 22 85 11 80 23 84 4 30 90 30 90 92 91 41 45 21 82 11 92 65 30 28 67 74 57 95 36 16 31 78 66 2 77 6 73 83 20 41 62 45 44 92 94 96 28 77 47 76 12 87 1 47 80 42 85 46 91 65 72 23 39 4 58 21 96 37 80 83 33 66 50 84 21 61 44 4 78 47 35 39 50 39 ...
output:
6 6 5 6 6 -1 0 4 6 7 7 6 6 2 7 8 6 8 6 4 6 5 5 3 0 4 5 6 6 5 5 5 6 5 5 6 7 -1 5 4 -1 6 4 -1 4 6 5 5 -1 6 6 7 0 -1 2 -1 5 -1 5 7 2 4 6 4 6 6 -1 6 7 6 6 7 6 -1 4 2 7 0 6 -1 6 2 -1 4 6 5 -1 7 3 5 0 -1 7 3 4 6 4 6 0 1 5 7 6 -1 -1 -1 6 5 5 5 3 3 3 -1 -1 2 3 5 6 -1 -1 9 -1 5 8 6 5 6 -1 3 5 5 -1 4 5 6 -1 6...
result:
wrong answer 16th numbers differ - expected: '7', found: '8'