QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768723 | #9738. Make It Divisible | TauLee01# | WA | 0ms | 3636kb | C++23 | 1.9kb | 2024-11-21 13:59:29 | 2024-11-21 13:59:29 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cout << #x << "=" << x << endl
//using i128 = __int128_t;
#define int long long
typedef pair<int,int> PII;
typedef long long ll;
inline void read(int &x){
char ch=getchar();int f=1;x=0;
while(!isdigit(ch) && ch^'-') ch=getchar();
if(ch=='-') f=-1,ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
x*=f;
}
void write(int x){
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
int n,k;
void rCL(){
cin>>n>>k;
vector<int>a(n+1);
int mx=2e9;
for(int i=1;i<=n;i++){
cin>>a[i];
mx=min(mx,a[i]);
}
if(n==1){
cout<<k<<' ';
cout<<(1+k)*k/2<<endl;
return ;
}
int g=a[2]-a[1];
for(int i=3;i<=n;i++){
g=gcd(g,a[i]-a[i-1]);
}
//cout<<g<<endl;
int res=0;
int cnt=0;
map<int,int>mp;
for(int i=1;i<=sqrt(g);i++){
if(g%i==0){
int a=i;
int b=g/i;
if(a==b){
if(!mp[a-mx]&&a-mx>0&&a-mx<=k){
mp[a-mx]=1;
res+=a-mx;
cnt++;
}
}else{
if(!mp[a-mx]&&a-mx>0&&a-mx<=k){
mp[a-mx]=1;
res+=a-mx;
cnt++;
}
if(!mp[b-mx]&&b-mx>0&&a-mx<=k){
mp[b-mx]=1;
res+=b-mx;
cnt++;
}
}
}
}
cout<<cnt<<' ';
cout<<res<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int O_o;
cin>>O_o;
while(O_o--){
rCL();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 3636kb
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'