QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#868080 | #9738. Make It Divisible | Nana7# | WA | 1ms | 3584kb | C++20 | 914b | 2025-01-24 11:52:14 | 2025-01-24 11:52:18 |
Judging History
answer
#include<bits/stdc++.h>
#define I inline
#define ll long long
using namespace std;
const int N = 50010;
int a[N],n,k;
int gcd(int x,int y) {
if(!y) return x;
return gcd(y,x%y);
}
I bool ck(int v) {
int ad=v-a[1];
if(ad<=0) return 0;
if(ad>k) return 0;
for(int i=2;i<=n;++i) {
if((a[i]+ad)%v) return 0;
}
//cout<<"!!"<<v<<endl;
return 1;
}
I void solve() {
cin>>n>>k;
for(int i=1;i<=n;++i) cin>>a[i];
sort(a+1,a+1+n);
bool f=1;
for(int i=1;i<n;++i) if(a[i]!=a[i+1]) f=0;
if(f) {
cout<<k<<' '<<1ll*k*(k+1)/2<<endl;
return ;
}
int ng=a[2]-a[1];
for(int i=3;i<=n;++i) ng=gcd(ng,a[i]-a[i-1]);
ll cnt=0,sum=0;
for(int i=1;i*i<=ng;++i) {
if(ng%i==0) {
if(ck(i)) cnt++,sum+=i-a[1];
if(ng/i!=i) {
if(ck(ng/i)) cnt++,sum+=ng/i-a[1];
}
}
}
cout<<cnt<<' '<<sum<<endl;
}
int main()
{
int T; cin>>T;
while(T--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
3 5 10 7 79 1 7 1 2 1000000000 1 2 1 100 1000000000
output:
3 8 0 0 100 5050
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3584kb
input:
4 201 1000000000 1 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5...
output:
0 0 1 1 0 0 0 0
result:
wrong answer 2nd lines differ - expected: '0 0', found: '1 1'