QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#834143 | #9738. Make It Divisible | remain11# | WA | 7ms | 12372kb | C++20 | 2.4kb | 2024-12-27 11:55:18 | 2024-12-27 11:55:18 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int GCD(int X,int Y)
{
if(!X||!Y)
return X^Y;
return GCD(Y,X%Y);
}
int ABS(int X)
{
return (X>0?X:-X);
}
int B[50001];
vector<int>Map;
int Log[50001];
int STgcd[21][50001];
int STmin[21][50001];
void Clear()
{
Map.clear();
}
int Min(int X,int Y)
{
return B[X]>B[Y]?Y:X;
}
int Querymin(int L,int R)
{
int Lg=Log[R-L+1];
return Min(STmin[Lg][L],STmin[Lg][R-(1<<Lg)+1]);
}
int Querygcd(int L,int R)
{
int Lg=Log[R-L+1];
return GCD(STgcd[Lg][L],STgcd[Lg][R-(1<<Lg)+1]);
}
void Check(int L,int R)
{
if(L>=R)return;
int Mini=Querymin(L,R);
int Gcd=Querygcd(L,R-1);
// printf("%d %d %d %d\n",L,R,Mini,Gcd);
for(int i=0;i<Map.size();++i)
{
int Now=Map[i];
if(!Now)continue;
if(Gcd%(Map[i]+B[Mini]))
Map[i]=0;
}
Check(L,Mini-1);
Check(Mini+1,R);
}
void Solve()
{
ll N,K;
scanf("%lld%lld",&N,&K);
int Maxi=0,Mini=1e9+7;
for(int i=1;i<=N;++i)
{
scanf("%d",&B[i]);
Maxi=max(B[i],Maxi);
Mini=min(Mini,B[i]);
STmin[0][i]=i;
}
if(Maxi==Mini)
{
printf("%lld %lld\n",K,(K+1)*K>>1);
return;
}
int Gcd=0;
for(int i=1;i<N;++i)
{
STgcd[0][i]=ABS(B[i+1]-B[i]);
}
for(int i=1;i<=Log[N];++i)
{
int End=N-(1<<i)+1;
for(int j=1;j<=End;++j)
{
STmin[i][j]=Min(STmin[i-1][j],STmin[i-1][j+(1<<(i-1))]);
STgcd[i][j]=GCD(STgcd[i-1][j],STgcd[i-1][j+(1<<(i-1))]);
}
}
Gcd=Querygcd(1,N-1);
Mini=Querymin(1,N);
for(int i=1;i*i<=Gcd;++i)
{
if(Gcd%i)continue;
if(i>B[Mini]&&i<=K)
{
Map.push_back(i-B[Mini]);
}
if(i*i!=Gcd&&Gcd/i>B[Mini]&&Gcd/i<=K)
{
Map.push_back(Gcd/i-B[Mini]);
}
}
Check(1,Mini-1);
Check(Mini+1,N);
ll Ansa=0,Ansb=0;
for(int i=0;i<Map.size();++i)
{
if(Map[i])
{
++Ansa;
Ansb+=Map[i];
}
}
printf("%lld %lld\n",Ansa,Ansb);
}
int main()
{
int T;
scanf("%d",&T);
Log[0]=-1;
for(int i=1;i<=5e4;++i)
Log[i]=Log[i>>1]+1;
while(T--)
{
Clear();
Solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12084kb
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: 10176kb
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: 0ms
memory: 12144kb
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: 0ms
memory: 12008kb
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: 7ms
memory: 12372kb
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: 0ms
memory: 11820kb
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: 4ms
memory: 6224kb
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'