fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #define rep(i, a, b) for(int i=(a); i<(b); i++)
  5. #define repi(i, a, b) for(int i=(a); i>(b); i--)
  6. #define db(x) (cerr << #x << ": " << (x) << '\n')
  7. #define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
  8. #define tests(t) int t; cin >> t; while(t--)
  9. #define iceil(n, x) (((n) + (x) - 1) / (x))
  10. #define ll long long
  11. #define gcd __gcd
  12. #define pb push_back
  13. #define pf push_front
  14. #define pob pop_back
  15. #define pof pop_front
  16. #define sz size()
  17. #define all(v) (v).begin(), (v).end()
  18. #define uni(v) sort(all(v)); (v).erase(unique(all(v)), (v).end());
  19. #define pii pair<int, int>
  20. #define vi vector<int>
  21. #define vpii vector<pii>
  22. #define vvi vector<vi>
  23. #define fi first
  24. #define se second
  25. #define umap unordered_map
  26. #define uset unordered_set
  27. #define pqueue priority_queue
  28. #define si(a) scanf("%d", &a)
  29. #define sll(a) scanf("%lld", &a)
  30. #define bitcount(x) __builtin_popcount(x)
  31. #define cps CLOCKS_PER_SEC
  32. #define PI acos(-1.0l)
  33. #define EPS 1e-6
  34. #define mod 1000000007
  35. #define MOD 1000000007
  36. #define N 100005
  37. using namespace std;
  38.  
  39. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  40. template <typename Arg1>
  41. void __f(const char* name, Arg1&& arg1){
  42.     cerr << name << " : " << arg1 << '\n';
  43. }
  44. template <typename Arg1, typename... Args>
  45. void __f(const char* names, Arg1&& arg1, Args&&... args){
  46.     const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  47. }
  48.  
  49. template<typename T>
  50. using minpq = priority_queue<T, vector<T>, greater<T>>;
  51.  
  52. template<typename T>
  53. using maxpq = priority_queue<T>;
  54.  
  55. //All indexing is 0-based
  56. using namespace __gnu_pbds;
  57. typedef tree<int, null_type, less<int>, rb_tree_tag,
  58.              tree_order_statistics_node_update> ordered_set;
  59. //methods: find_by_order(k); & order_of_key(k);
  60. //To make it an ordered_multiset, use pairs of (value, time_of_insertion)
  61. //to distinguish values which are similar.
  62.  
  63. template<class key, class value, class cmp = std::less<key>>
  64. using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  65. //ordered_map<int, int> my_map;
  66.  
  67.  
  68. //Returns no. of values x for which ceil(n / x) == y (y must be > 1).
  69. inline ll CC(ll n, ll y) { return iceil(n, y-1) - iceil(n, y); }
  70.  
  71. //Returns no. of values x for which floor(n / x) == y
  72. inline ll FF(ll n, ll y) { return n / y - n / (y+1); }
  73.  
  74. //a and b are assumed to be taken modulo p
  75. inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c;}
  76. inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c;}
  77. inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p;}
  78.  
  79. #define int ll
  80. //#define trace(...) 42
  81.  
  82. //Links: 
  83. //Linear sieve and Multiplicative functions: https://c...content-available-to-author-only...s.com/blog/entry/54090
  84. //Mobius Inversion:                          https://c...content-available-to-author-only...s.com/blog/entry/53925
  85.  
  86. /* Logic used: Every composite no. can be uniquely represented as 
  87.     q = i * p; where p is the smallest prime factor and i >= p.
  88.     We just need to ensure that every composite no. gets marked exactly once
  89.     and we do that when we reach i by considering all primes p <= i
  90.     and marking the corresponding nos. (i * p) as composites.
  91. */
  92.  
  93. int M[N], cnt[N];
  94. bool isPrime[N];
  95. vector<int> primes;
  96.  
  97. //Computes the list of all prime numbers <= n and stores in prime.
  98. //Also computes the value of the multiplicative function, func(i) for all i from 1 to n
  99. //and stores in f[i].
  100. void sieve(int n) {
  101.     fill(isPrime, isPrime+n+1, 1);
  102.     primes.clear();
  103.  
  104.     M[1] = 1;
  105.     for(int i = 2; i <= n; i++) {
  106.         if(isPrime[i]) {
  107.             primes.push_back(i);
  108.             M[i] = -1; cnt[i] = 1;
  109.         }
  110.         for(int p : primes) {
  111.             if(i * 1ll * p > n) break;
  112.             isPrime[i*p] = 0;
  113.             if(i % p == 0) {
  114.                 M[i*p] = 0; //Since p^2 divides i
  115.                 cnt[i*p] = cnt[i] + 1;
  116.                 break;
  117.                 //if p divides i then for all primes q > p,
  118.                 //the spf of i*q would be p and not q.
  119.             }
  120.             else {
  121.                 M[i*p] = M[i] * M[p];
  122.                 cnt[i*p] = 1;
  123.             }
  124.         }
  125.     }
  126. }
  127.  
  128. void prep() {
  129.     sieve(N-5);
  130. }
  131.  
  132. int solve(int b, int d, int k) {
  133.     int m = min(b/k, d/k);
  134.     int ans = 0;
  135.  
  136.     for(int l = 1; l <= m; l++) {
  137.         ans += M[l] * (b/k/l) * (d/k/l);
  138.     }
  139.     return ans;
  140. }
  141.  
  142. int32_t main()
  143. {   
  144.     #ifdef CP
  145.         freopen("/home/tarun/Desktop/input.txt", "r", stdin);
  146.     //  freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  147.     #endif
  148.     sync;
  149.     clock_t clk = clock();
  150.     //cerr << "I will return...\n";
  151.  
  152.     prep();
  153.  
  154.     int oo = 1;
  155.     tests(t) {
  156.         cout << "Case " << oo++ << ": ";
  157.         int a, b, c, d, k; cin >> a >> b >> c >> d >> k;
  158.         int m = min(b, d);
  159.         if(k == 0 || m < k) {
  160.             cout << 0 << '\n'; continue;
  161.         }
  162.  
  163.         int X = solve(b, d, k);
  164.         int Y = solve(m, m, k);
  165.  
  166.         int ans = X - (Y-1)/2;
  167.  
  168.         //trace(X, Y);
  169.  
  170.         cout << ans << '\n';
  171.     }
  172.  
  173.     //cerr << "...don't you ever hang your head.\n";
  174.     //cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
  175. }
  176.  
  177. //Compile using:
  178. //g++ -o filename.exe --std=c++11 filename.cpp
  179. //Use -D CP for defining a macro CP in the local environment
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
Success #stdin #stdout 0s 17016KB
comments (?)
stdin
copy 
2
1 3 1 5 1
1 11014 1 14409 9
stdout
copy 
Case 1: 9
Case 2: 736427
https://ideone.com/WzA6dV
language:
C++14 (gcc 8.3)
created:
5 years 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!