QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #878559 | #9738. Make It Divisible | windcity# | WA | 1ms | 3840kb | C++14 | 1.3kb | 2025-02-01 16:01:30 | 2025-02-01 16:01:31 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[50001];
inline int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d%d",&n,&k);
for(register int i=1;i<=n;++i)scanf("%d",&a[i]);
if(n==1)printf("%d %lld\n",k,1ll*k*(k+1)/2);
else{
long long sum=0;int ans=0,minn=a[1],m=0;
for(register int i=2;i<=n;++i)minn=min(minn,a[i]);
for(register int i=1;i<=n;++i)
if(a[i]!=minn&&!m)m=a[i]-a[1];
else if(a[i]!=minn)m=gcd(m,a[i]-minn);
if(m==0)printf("%d %lld\n",k,1ll*k*(k+1)/2);
else{
int x=min(m,minn+k);
for(register int i=minn+1;i<=x;++i){
if(m%i)continue;
int t=i-minn,flag=1;
for(register int j=1;j<=n&&flag;++j){
int s=a[j]+t;
for(register int k=j+1;k<=n&&flag;++k)
if(a[k]+t<=s){
if(s%(a[k]+t)!=0)flag=0;
else s=a[k]+t;
}
else{
if((a[k]+t)%s!=0)flag=0;
}
}
if(flag){++ans;sum+=1ll*t;}
}
printf("%d %lld\n",ans,sum);
}
}
}
return 0;
}
//k+minn|a[i]-minn,1<=i<=n
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
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: 3840kb
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: 1ms
memory: 3840kb
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 1000000000 500000000500000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 35th lines differ - expected: '0 0', found: '1000000000 500000000500000000'