QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#776442 | #9738. Make It Divisible | zqx | WA | 2ms | 5740kb | C++20 | 1.4kb | 2024-11-23 18:41:56 | 2024-11-23 18:41:56 |
Judging History
answer
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define inf 0X7fffffff
#define int long long
using namespace std;
const int N=2e5+9;
int read(int &x){
int dat=0,oko=1;char chc=getchar();
while(chc<'0'||chc>'9'){if(chc=='-')oko=-1;chc=getchar();}
while(chc>='0'&&chc<='9'){dat=dat*10+chc-'0';chc=getchar();}
x=dat*oko;return x;
}int T,n,k,_gcd,a[N],b[N],ans1,ans2;
int gcd(int x,int y){
while(y){
x%=y;swap(x,y);
}return x;
}bool check(int x){
for(int i=1;i<=n;i++)b[i]=a[i]+x;
for(int i=2;i<=n;i++){
if(b[i]%b[i-1])return false;
}return true;
}
void solve(){
cin>>n>>k;ans1=0,ans2=0;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);_gcd=0;
for(int i=2;i<=n;i++){
_gcd=gcd(_gcd,a[i]-a[i-1]);
}if(!_gcd){
cout<<k<<" "<<(((k+1)*k)>>1)<<"\n";
return;
}for(int i=1;i*i<=_gcd;i++){
if(_gcd%i)continue;
if(a[1]+k>=i&&i>a[1]){
if(check(i-a[i])){
ans1++;ans2+=i-a[1];
}
}int j=_gcd/i;if(i==j)continue;
if(a[1]+k>=j&&j>a[1]){
if(check(j-a[1])){
ans1++;ans2+=j-a[1];
}
}
}cout<<ans1<<" "<<ans2<<"\n";
}
signed main(){
cin>>T;
while(T--)solve();
return 0;
}
/*
3
5 10
7 79 1 7 1
2 1000000000
1 2
1 10000
1000000000
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5740kb
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: 0
Accepted
time: 0ms
memory: 3632kb
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 0 0 0 0 0 0
result:
ok 4 lines
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3656kb
input:
500 4 1000000000 8 14 24 18 4 1000000000 17 10 18 14 4 1000000000 6 17 19 19 4 1000000000 15 14 15 25 4 1000000000 16 16 5 25 4 1000000000 4 30 20 5 4 1000000000 11 4 23 9 4 1000000000 14 25 13 2 4 1000000000 18 18 1 15 4 1000000000 22 22 22 28 4 1000000000 15 17 17 10 4 1000000000 22 14 13 25 4 100...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 178th lines differ - expected: '1 2', found: '0 0'