QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#627292 | #5301. Modulo Ruins the Legend | qilou | WA | 26ms | 7728kb | C++23 | 2.2kb | 2024-10-10 15:27:47 | 2024-10-10 15:27:48 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const int N=5e5+10,inf=1e9+10;
int n,m,k,sum=0,mod,ns[N];
int vis[N];
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1;y=0;
return a;
}
else
{
ll tx,ty;
ll d=exgcd(b,a%b,tx,ty);
x=ty;y=tx-(a/b)*ty;
return d;
}
}
int cacu(){
int res=0;
if(n==1){
return 1%mod;
}
int v=(1+n);
if(n%2==0){
res=v*n/2;
}else {
res=n/2*v+v/2;
}
return res%mod;
}
void solve(){
cin>>n>>mod;
for(int i=1;i<=n;i++){
cin>>ns[i];
sum+=ns[i];
}
if(mod==1){
cout<<0<<endl;
cout<<0<<" "<<0<<endl;
return ;
}
int all=cacu();
sum%=mod;
// cout<<sum<<endl;
int now=mod-sum;
for(int i=0;i<min(sum,n);i++){
int a=n,b=all,k=(now+i)%mod,x=0,y=0;
// cout<<a<<" "<<b<<endl;
int d=exgcd(a,b,x,y);
// cout<<k<<" "<<d<<endl;
// cout<<x<<" "<<y<<endl;
if(k%d==0){
x=x*k/d;
y=(k-a*x)/b;
x%=mod;
y%=mod;
int ans1=x,ans2=y;
if(x<0){
int v=x*n;
// cout<<x<<" "<<y<<" "<<v<<endl;
int tv=mod+v%mod;
int o=0,oo=0;
// cout<<tv<<endl;
int p=exgcd(a,mod,o,oo)%mod;
// cout<<o<<" "<<oo<<endl;
o*=tv/p;
oo=(tv-a*o)/mod;
ans1=o;
ans2=y;
}
if(y<0){
int v=y*all;
int tv=mod+v%mod;
int o=0,oo=0;
int p=exgcd(all,mod,o,oo)%mod;
o*=tv/p;
oo=(tv-a*o)/mod;
ans1=x;
ans2=oo;
}
cout<<i<<endl;
cout<<ans1%mod<<" "<<ans2%mod<<endl;
return ;
}
}
cout<<sum<<endl;
cout<<0<<" "<<0<<endl;
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int T=1;
// cin>>T;
while(T--){
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5676kb
input:
6 24 1 1 4 5 1 4
output:
1 3 3
result:
ok ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
7 29 1 9 1 9 8 1 0
output:
0 0 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
1 1 0
output:
0 0 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 5672kb
input:
1 1000000000 963837005
output:
0 0 36162995
result:
ok ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
2 1 0 0
output:
0 0 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
2 1000000000 948507269 461613424
output:
0 410120693 589879307
result:
ok ok
Test #7:
score: 0
Accepted
time: 6ms
memory: 7728kb
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: 22ms
memory: 5668kb
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: 26ms
memory: 7712kb
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