oj.uz

Submission #9691

# Submission time Handle Problem Language Result Execution time Memory
9691 2014-09-28T08:08:08 Z ainu7 Xtreme gcd sum (kriii2_X) C++
0 / 4
 724 ms 17300 KB 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

const int max_n = 1000000;
int noprime[max_n+1], mm[max_n+1], trans[max_n+1], inv[max_n+1];
long long mmod = 1000000007;

int inv_mod(int a, int b) {
  if (a == 1) return b;
  int div = mmod / a + 1;
  return inv_mod((a * (long long)div) % mmod, (b * (long long)div) % mmod);
}

int main()
{
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i=0; i<n; i++) cin >> a[i] >> b[i];

/*  if (n == 2) {
    int s = 0;
    for (int i=a[0]; i<=b[0]; i++) for (int j=a[1]; j<=b[1]; j++) s = (s + __gcd(i, j)) % mmod;
    printf("%d\n", s);
  }*/
  noprime[1] = 1;
  for (int i=2; i<=max_n; i++)
    if (!noprime[i])
      for (int j=i*2; j<=max_n; j+=i)
        noprime[j] = 1;

  for (int i=1; i<=max_n; i++) mm[i] = i;
  for (int i=1; i<=max_n; i++)
    for (int j=i*2; j<=max_n; j+=i)
      mm[j] -= mm[i];

  for (int i=1; i<=max_n; i++) inv[i] = inv_mod(i, 1);

  for (int i=1; i<=max_n; i++) trans[i] = 1;
  for (int i=0; i<n; i++) {
    trans[1] = (trans[1] * (long long)(b[i] - a[i] + 1)) % mmod;
    int num = b[i] - a[i] + 1;
    int prv = 1;
    while (1) {
//      printf("%d %d\n", num, prv);
      int bb = b[i] / prv;
      int aa = (a[i]-1) / prv;
      int nxt = 9999999;
      if (bb) nxt = min(nxt, b[i] / bb + 1);
      if (aa) nxt = min(nxt, (a[i]-1) / aa + 1);
      if (nxt > max_n) break;
      int num2 = b[i]/nxt - (a[i]-1)/nxt;

      trans[nxt] = (trans[nxt] * (long long)num2) % mmod;
      trans[nxt] = (trans[nxt] * (long long)inv[num]) % mmod;

      num = num2;
      prv = nxt;
    }
  }

  int res = 0;
  int pp = 1;
  for (int i=1; i<=max_n; i++) {
    pp = (pp * (long long)trans[i]) % mmod;
    int mult = pp;
    res = (res + mult * (long long)mm[i]) % mmod;
    if (res < 0) res += mmod;
  }
  cout << res << endl;
}

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 17300 KB Output is correct
2 Correct 716 ms 17300 KB Output is correct
3 Correct 712 ms 17300 KB Output is correct
4 Correct 716 ms 17300 KB Output is correct
5 Correct 716 ms 17300 KB Output is correct
6 Correct 716 ms 17300 KB Output is correct
7 Correct 716 ms 17300 KB Output is correct
8 Correct 700 ms 17300 KB Output is correct
9 Correct 716 ms 17300 KB Output is correct
10 Correct 712 ms 17300 KB Output is correct
11 Correct 724 ms 17300 KB Output is correct
12 Correct 720 ms 17300 KB Output is correct
13 Correct 724 ms 17300 KB Output is correct
14 Correct 716 ms 17300 KB Output is correct
15 Correct 716 ms 17300 KB Output is correct
16 Incorrect 712 ms 17300 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -