fork download
copy 
  1. /*
  2.  *  E. Mathematician Montu | SRBD Code Contest - 2024 (Round 1)
  3.  *  Author: Sohom Sahaun | @sohomsahaun | CF: sahaun
  4.  */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
  10. using ll = long long;
  11.  
  12. int main() {
  13.   FAST;
  14.  
  15.   int tc = 1, ti;
  16.   cin >> tc;
  17.  
  18.   for (ti = 1; ti <= tc; ++ti) {
  19.     ll n, m, x, i, j, sz;
  20.     cin >> n >> m;
  21.  
  22.     vector<ll> divs;
  23.     for (i = 1; i*i <= n; ++i) {
  24.       if (n % i == 0) {
  25.         divs.push_back(i);
  26.         if (i*i != n) divs.push_back(n/i);
  27.       }
  28.     }
  29.     sort(divs.begin(), divs.end());
  30.     sz = divs.size();
  31.  
  32.     map<ll,ll> id;
  33.     for (i = 0; i < sz; ++i) id[divs[i]] = i;
  34.  
  35.     vector<ll> ans(sz);
  36.     for (i = sz-1; i >= 0; --i) {
  37.       x = divs[i];
  38.       ans[i] = n / x;
  39.       for (j = i+1; j < sz; ++j) {
  40.         if (divs[j] % x == 0) {
  41.           ans[i] -= ans[j];
  42.         }
  43.       }
  44.     }
  45.  
  46.     vector<ll> a(m);
  47.     for (i = 0; i < m; ++i) cin >> a[i];
  48.  
  49.     cout << "Case " << ti << ": ";
  50.     for (i = 0; i < m; ++i) {
  51.       x = 0;
  52.       if (n % a[i] == 0) {
  53.         x = ans[id[a[i]]];
  54.       }
  55.       cout << x << " ";
  56.     }
  57.     cout << "\n";
  58.   }
  59.  
  60.   return 0;
  61. }
  62.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
2
20 5
1 2 3 4 5
30 6
1 2 3 4 5 6
stdout
copy 
Case 1: 8 4 0 4 2 
Case 2: 8 8 4 0 2 4
https://ideone.com/Hc0Q79
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!