QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#750208#9738. Make It DivisiblezqxWA 1ms3640kbC++141.7kb2024-11-15 13:25:152024-11-15 13:25:15

Judging History

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

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

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 55;
const int INF = 1e18+ 7 ;
const int MOD = 998244353;

#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) ; 
      // cout << j << " " << cha[i] / j << endl ; 
      }
    }
  } 
// 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
  // o = x + a ;
  // x = o - a ;
  vector<int> ans ;  
  int tot = 0 ; 
  for(auto o : se) {
    if(o == 0) continue ; 

      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() ; 
  // system("pause") ;
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3640kb

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: 1ms
memory: 3612kb

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:

wrong answer 178th lines differ - expected: '1 2', found: '0 0'