QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768139 | #9738. Make It Divisible | i_wish_a_girl_friend | WA | 0ms | 3668kb | C++23 | 3.3kb | 2024-11-21 01:03:29 | 2024-11-21 01:03:30 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
//const int mod=998244353;
int qpw(int a,int b,int mod){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
//int inv(int x){return qpw(x,mod-2);}
const int MAX_N = 5e4+10;
const int LOG = 17; // log2(MAX_N) 的上界
int n, a[MAX_N];
int f[MAX_N][LOG]; // 倍增表:up[i][k] 表示从 i 向上跳 2^k 步后的节点
int gcd_table[MAX_N][LOG]; // gcd_table[i][k] 表示从 i 到 up[i][k] 的 GCD 值
int parent[MAX_N]; // 笛卡尔树中的父节点
int depth[MAX_N]; // 每个节点的深度
int dp_gcd[17][(int)5e4 + 1];
// 求 GCD
int gcd(int a, int b) {
return b?gcd(b,a%b):a;
}
void solve(){
int k;cin>>n>>k;
set<int>sb;
vector<int>ls_min(n+1),rs_min(n+1);
int root_min;
for(int i=1,x;i<=n;i++)cin>>a[i],sb.insert(a[i]);
if(sb.size()==1){
cout<<k<<" "<<k*(k+1)/2<<'\n';
return;
}
vector<int>sta(n+1);
function<void()>build_min=[&](){
int top=0,cur=0;
for(int i=1;i<=n;i++){
cur=top;
while(cur&&a[sta[cur]]>a[i])cur--;
if(cur)rs_min[sta[cur]]=i;
if(cur<top)ls_min[i]=sta[cur+1];
sta[++cur]=i;
top=cur;
}
};
auto query_min=[&](int l,int r){
int x=root_min;
for(;;x=(r<x?ls_min[x]:rs_min[x]))if(l<=x&&x<=r)return x;
};
int gc=0;
vector<int>b(n+1);
for(int i=2;i<=n;i++){
gc=gcd(gc,b[i]=abs(a[i]-a[i-1]));
}
build_min();
root_min=sta[1];
set<int>dp,ndp;
// cout<<query(2,2)<<'\n';
function<int(int,int)> dfs = [&]( int l, int r)->int
{
if (l == r)
{
return a[l];
}else if(l>r)return 0ll;
int mid = query_min(l, r);
if(l==1&&r==n) {
for (int i = 1; i * i <= gc; i++) {
if (gc % i)
continue;
for (auto j: (i * i == gc ? vector<int>{i} : vector<int>{i, gc / i})) {
{
if (j > a[mid] and j - a[mid] <= k)
dp.insert(j - a[mid]);
}
}
}
int a=dfs(l, mid - 1);
int b=dfs(mid + 1, r);
return gc;
}else {
int L=dfs(l,mid-1);
int R=dfs(mid+1,r);
int G=gcd(L,R);
G=gcd(G,b[mid]);
for(int x:dp){
// cout<<x<<" ";
if(G%(x+a[mid]))continue;
ndp.insert(x);
}
// cout<<'\n';
dp.swap(ndp);
ndp.clear();
return G;
}
};
int ooo=dfs(1, n);
int sum=0;
for(int x:dp)sum+=x;
cout<<dp.size()<<" "<<sum<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
cin>>_;
while(_--)solve();
}
/*
3
1
3 1000000000
230 286458 41263680
1
10 1000000000
230 286458 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3668kb
input:
3 5 10 7 79 1 7 1 2 1000000000 1 2 1 100 1000000000
output:
0 0 0 0 100 5050
result:
wrong answer 1st lines differ - expected: '3 8', found: '0 0'