QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#750172#9738. Make It DivisiblezqxWA 2ms3620kbC++141.4kb2024-11-15 13:12:062024-11-15 13:12:07

Judging History

你现在查看的是最新测评结果

  • [2024-11-27 18:44:44]
  • hack成功,自动添加数据
  • (/hack/1263)
  • [2024-11-15 13:12:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3620kb
  • [2024-11-15 13:12:06]
  • 提交

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: 0ms
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: 3592kb

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: 3568kb

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'