QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750169 | #9738. Make It Divisible | zqx | WA | 2ms | 3620kb | C++14 | 1.4kb | 2024-11-15 13:10:46 | 2024-11-15 13:10:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 55;
const int INF = 1e9 + 7;
const int MOD = 998244353;
#define int long long
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
inline void solve() {
int n , k ; cin >> n >> k ;
vector<int> a(n + 1) ;
int mini = INF ;
for(int i = 1 ; i <= n ; i ++ ) {
cin >> a[i] ;
mini = min(a[i],mini) ;
}
if(n == 1) {
cout << k << " " << k * (k + 1) / 2 << endl ; return ;
}
// o = x + a ;
vector<int> cha(n + 1) , gc(n + 1,0) ;
for(int i = 1 ; i < n ; i ++ ) cha[i] = abs(a[i + 1] - a[i]) ,gc[i] = __gcd(cha[i],gc[i - 1]) ;
set<int> se ;
for(int i = 1 ; i < n ; i ++ ) {
for(int j = 1 ; j * j <= cha[i] ; j ++ ) {
if(cha[i] % j == 0 ) se.insert(j) ;
se.insert(cha[i] / j) ;
}
}
// o = x + a ;
// x = o - a ;
vector<int> ans ;
int tot = 0 ;
for(auto o : se) {
int ok = 1 ;
int x = o - mini ;
if(x > k) break ;
if(x == 0) continue ;
for(int i = 1 ; i < n ; i ++ ) {
int ts = min(a[i + 1],a[i]) ;
if(gc[i] % (ts + x) != 0) {
ok = 0 ; break ;
}
}
if(ok == 1) ans.push_back(x) , tot += x ;
}
cout << ans.size() << " " << tot << endl ;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t ; cin >> t ;
while(t -- ) solve() ;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
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: 3572kb
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: 2ms
memory: 3508kb
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 1 -4 0 0 0 0 0 0 0 0 4 -76 0 0 1 -12 0 0 0 0 0 0 0 0 0 0 1 -2 0 0 0 0 0 0 0 0 0 0 1 -1 0 0 1 -9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 -64 0 0 0 0 0 0 0 0 0 0 1 -9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -3 0 0 0 0 0 0 ...
result:
wrong answer 5th lines differ - expected: '0 0', found: '1 -4'