Submission #9681

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9681	2014-09-28T08:04:27 Z	ainu7	Xtreme gcd sum (kriii2_X)	C++	0 / 4	4000 ms	17296 KB

X

#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];

  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) {
      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	Execution timed out	4000 ms	17296 KB	Program timed out
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 3.0

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