QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#627292#5301. Modulo Ruins the LegendqilouWA 26ms7728kbC++232.2kb2024-10-10 15:27:472024-10-10 15:27:48

Judging History

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

  • [2024-10-10 15:27:48]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:7728kb
  • [2024-10-10 15:27:47]
  • 提交

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