QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#748665 | #9738. Make It Divisible | Kir1same | WA | 15ms | 11232kb | C++14 | 2.4kb | 2024-11-14 21:01:15 | 2024-11-14 21:01:15 |
Judging History
answer
#include <bits/stdc++.h>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=5e4+10;
int minn[N][20],lg[N],n,k,b[N],a[N],cnt,num[N];
struct TREE
{
int dat;
}tr[N<<2];
struct node
{
int l,r,pos;
}x[N];
int gcd(int x,int y)
{
if(!x||!y) return x|y;
return __gcd(x,y);
}
void build(int p,int l,int r)
{
if(l==r) {tr[p].dat=a[l]<0?-a[l]:a[l];return;}
build(ls(p),l,mid);
build(rs(p),mid+1,r);
tr[p].dat=gcd(tr[ls(p)].dat,tr[rs(p)].dat);
}
int query(int p,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr) return tr[p].dat;
if(ll<=mid&&rr>mid) return gcd(query(ls(p),l,mid,ll,rr),query(rs(p),mid+1,r,ll,rr));
if(ll<=mid) return query(ls(p),l,mid,ll,rr);
else return query(rs(p),mid+1,r,ll,rr);
}
int query(int l,int r)
{
int k=lg[r-l+1];
int pos1=minn[l][k],pos2=minn[r-(1<<k)+1][k];
return b[pos1]<b[pos2]?pos1:pos2;
}
void solve(int l,int r)
{
if(l>=r) return;
int pos=query(l,r);
x[++cnt]=(node){l,r,pos};
solve(l,pos-1);solve(pos+1,r);
}
int main()
{
for(int i=2;i<N;i++) lg[i]=lg[i>>1]+1;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&k);
bool flag=true;int maxx=0;
for(int i=1;i<=n;i++)
scanf("%d",&b[i]),a[i]=b[i]-b[i-1],flag&=(i==1||a[i]==0),maxx=max(maxx,b[i]);
if(flag)
{
printf("%d %lld\n",k,1ll*k*(k+1)/2);
continue;
}
build(1,1,n);
for(int i=1;i<=n;i++)
minn[i][0]=i;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
minn[i][j]=b[minn[i][j-1]]<b[minn[i+(1<<j-1)][j-1]]?minn[i][j-1]:minn[i+(1<<j-1)][j-1];
cnt=0;
solve(1,n);
for(int i=1;i<=cnt;i++)
num[i]=query(1,1,n,x[i].l+1,x[i].r);
maxx=sqrt(maxx)*2;
long long ans=0,ans1=0;
vector<long long> ori;
long long GCD = num[1];
for (int i=1;i*i<=GCD;i++) {
if (GCD % i == 0) {
ori.push_back(i);
if (i*i != GCD) ori.push_back(GCD / i);
}
}
int mn=*min_element(b+1,b+1+n);
for(int t:ori)
{
bool flag=true;
int i=t-mn;
if(i<=0 || t > k) continue;
for(int j=1;j<=cnt;j++)
if(!(num[j]%(b[x[j].pos]+i)==0&&(b[x[j].l]+i)%(b[x[j].pos]+i)==0))
{
flag=false;
break;
}
// cout<<"SS"<<i<<' '<<flag<<endl;
if(flag) ans++,ans1+=i;
}
printf("%lld %lld\n",ans,ans1);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4232kb
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: 1ms
memory: 4032kb
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: 0
Accepted
time: 1ms
memory: 4232kb
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:
ok 500 lines
Test #4:
score: 0
Accepted
time: 15ms
memory: 11152kb
input:
1 50000 1000000000 230 286458 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 ...
output:
0 0
result:
ok single line: '0 0'
Test #5:
score: 0
Accepted
time: 15ms
memory: 11136kb
input:
1 50000 1000000000 12087 1196491 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 553146...
output:
0 0
result:
ok single line: '0 0'
Test #6:
score: 0
Accepted
time: 15ms
memory: 11232kb
input:
1 50000 1000000000 2138984 42249920 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 3581...
output:
0 0
result:
ok single line: '0 0'
Test #7:
score: -100
Wrong Answer
time: 3ms
memory: 4020kb
input:
500 39 1000000000 75 7 7 381 41 1197 177 177 41 109 109 16 1197 177 41 381 1605 381 381 7 177 177 177 177 177 177 177 177 7 7 143 143 143 143 143 653 143 823 7 61 1000000000 327 327 327 327 405153474 327 405153474 327 810306621 810306621 810306621 810306621 810306621 810306621 810306621 810306621 81...
output:
0 0 25 631568356 13 18925862 0 0 2 6878 1 2 1 1 2 10 0 0 1 110 0 0 1 36 11 4796 1 29 1 4 6 2209209 0 0 3 8 1 2 9 30770061 1000000000 500000000500000000 1 3 1000000000 500000000500000000 0 0 1 5 1 1 6 6615501 3 8233825 2 1035 2 4 7 1288 0 0 1 3 16 1617883221 2 10 0 0 1 5739 15 102584 3 1100 100000000...
result:
wrong answer 4th lines differ - expected: '1 1', found: '0 0'