Tranvick

Untitled

Apr 23rd, 2012
465
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <memory.h>
  3. #include <cstdio>
  4. #include <time.h>
  5.  
  6. using namespace std;
  7.  
  8. const int nn = 1 << 20;
  9. int d[nn];
  10.  
  11. long long f(long long x) {
  12.     return x * (x+1) / 2;
  13. }
  14.  
  15. long long memo[nn * 2];
  16.  
  17. long long h(long long n, long long m) {
  18.     if (memo[n + m] >= 0) return memo[n + m];
  19.    
  20.     long long res = n * m;
  21.    
  22.     for (int i = 2; i <= n && i <= m; ++i)
  23.         res += h(n / i, m / i) * -1;
  24.    
  25.     return memo[n + m] = res;
  26. }
  27.  
  28. long long g(long long n, long long m) {
  29.     long long res = 0;
  30.    
  31.     memset(memo, -1, sizeof memo);
  32.    
  33.     for (int a = 1; a <= n && a <= m; ++a) {
  34.         res += h(n / a, m / a) * a;
  35.     }
  36.    
  37.     return res;
  38. }
  39.  
  40. long long solve(int n, int m, int a, int b) {
  41.     long long res = f(a-1) + f(b-1) + f(n-a) + f(m-b);
  42.     res += g(a - 1, b - 1);
  43.     res += g(a - 1, m - b);
  44.     res += g(n - a, b - 1);
  45.     res += g(n - a, m - b);
  46.     return res;
  47. }
  48.  
  49. int main() {
  50.     freopen("input.txt", "r", stdin);
  51.     freopen("output.txt", "w", stdout);
  52.    
  53.     for (int i = 2; i < nn; ++i) if (!d[i])
  54.         for (int j = i; j < nn; j += i) d[j] = i;
  55.    
  56.     int n, m, a, b;
  57.     cin >> n >> m >> b >> a;
  58.     long long res = solve(n, m, a, b);
  59.     cout << res << endl;
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment