QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #769139 | #5301. Modulo Ruins the Legend | 22016020736 | WA | 6ms | 5916kb | C++17 | 3.6kb | 2024-11-21 16:17:30 | 2024-11-21 16:17:31 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int arr[2000009];
inline int exgcd(int a, int b, int &x, int &y)
{
if(!b){x = 1;y = 0;}
else
{
exgcd(b, a % b, x, y);
int t = x;
x = y;y = t - (a / b) * y;
}
return 0;
}
void solve()
{
int n,m;
scanf("%lld%lld",&n,&m);
int ans,s,d;
for(int i=1;i<=n;i++)
{
scanf("%lld",&arr[i]);
}
int sum=0;
for(int i=1;i<=n;i++)
{
sum+=arr[i];
sum%=m;
}
int tmpsum=sum,tmpa=n%m,tmpb=(n+1)*n/2;
tmpb%=m;
if(sum==0)
{
///printf("0\n");
ans=0;
s=0,d=0;
///printf("0 0\n");
}
else
{
int a=n%m,b=(n+1)*n/2;
b%=m;
if(a==0&&b==0)
{
ans=sum;
s=0,d=0;
//printf("%lld\n",sum);
//printf("0 0\n");
}
else if(a==0)
{
int k=(m-sum+b-1)/b;
int ans1=sum,ans2=(sum+k*b)%m;
if(ans1<=ans2)
{
ans=ans1;s=0,d=0;
///printf("%lld\n",ans1);
///printf("0 0\n");
}
else
{
ans=ans2;
s=0;d=k;
///printf("%lld\n",asn2);
///printf("0 %lld\n",k);
}
}
else if(b==0)
{
swap(a,b);
int k=(m-sum+b-1)/b;
int ans1=sum,ans2=(sum+k*b)%m;
if(ans1<=ans2)
{
ans=ans1;
s=0,d=0;
/// printf("%lld\n",ans1);
///printf("0 0\n");
}
else
{
ans=ans2;
s=k,d=0;
///printf("%lld\n",asn2);
///printf("%lld 0\n",k);
}
}
else
{
sum=m-sum;///这是需求;
int gd=__gcd(a,b);
if((sum%gd)==0)
{
a/=gd,b/=gd,sum/=gd;
int x,y;///a*x+b*y=c;
exgcd(a,b,x,y);
x%=m;
x+=m;
x%=m;
y%=m;
y+=m;
y%=m;
x*=sum;x%=m;
y*=sum;y%=m;
ans=0;
s=x,d=y;
// printf("ab:%lld %lld %lld %lld\n",a,b,x,y);
}
else
{
sum=m-sum;
int k=(m-sum+gd-1)/gd;
if(sum<=(sum+k*gd%m)%m)
{
ans=sum;
s=0,d=0;
}
else
{
int x,y;
exgcd(a,b,x,y);
x%=m;
x+=m;
x%=m;
y%=m;
y+=m;
y%=m;
x*=k;x%=m;
y*=k;y%=m;
ans=(sum+k*gd)%m;
s=x,d=y;
}
}
}
}
///这边是check(),函数的意义;
int ss=0;
for(int i=1;i<=n;i++)
{
ss+=s+arr[i]+i*d%m;
ss%=m;
}
if(ss!=ans)
{
printf("%lld\n",arr[30400500405]);
// printf("WA ss,%lld ans,%lld\n",ss,ans);
// printf("tmpsum,%lld tmpa:%lld tmpb:%lld s:%lld d:%lld\n",tmpsum,tmpa,tmpb,s,d);
}
else
{
printf("%lld\n",ans);
printf("%lld %lld",s,d);
}
}
signed main()
{
int tt=1;
// scanf("%lld",&tt);
while(tt--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
input:
6 24 1 1 4 5 1 4
output:
1 15 3
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
7 29 1 9 1 9 8 1 0
output:
0 0 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
1 1 0
output:
0 0 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 1000000000 963837005
output:
0 0 36162995
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
2 1 0 0
output:
0 0 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 1000000000 948507269 461613424
output:
0 410120693 589879307
result:
ok ok
Test #7:
score: 0
Accepted
time: 6ms
memory: 4728kb
input:
100000 1 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 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 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 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...
output:
0 0 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 5ms
memory: 5916kb
input:
100000 1000000000 253614966 278270960 980235895 498158918 928430170 216003119 852570558 948400590 239257296 897053667 294741176 38297441 382677590 406314557 609468973 854148232 314532767 738191551 158215002 5865825 920471826 380037058 356271728 749175327 28319049 208101105 953758995 896570758 521930...
output:
46613 0 9281
result:
ok ok
Test #9:
score: -100
Wrong Answer
time: 4ms
memory: 4572kb
input:
100000 998244353 561002596 498658036 721339539 63377827 532179242 934651519 234198881 490149304 2056307 499913682 427679408 694677560 516580968 300129454 816286800 688594301 183049581 456627420 495848352 273497462 953217060 796225499 207179832 728054671 409492082 25003432 810431468 206421553 5569626...
output:
4 382707322 342878665
result:
wrong answer Participant answer greater than judge