Submission #9704

#	Time	Username	Problem	Language	Result	Execution time	Memory
9704		ainu7	Xtreme gcd sum (kriii2_X)	C++98	4 / 4	2380 ms	21208 KiB

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];
int zero_plus[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 == 3) {
    int s = 0;
    for (int i=a[0]; i<=b[0]; i++) for (int j=a[1]; j<=b[1]; j++) for (int k=a[2]; k<=b[2]; k++)
      s = (s + __gcd(i, __gcd(j, k))) % 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;

      if (num2 == 0) zero_plus[nxt] ++; else trans[nxt] = (trans[nxt] * (long long)num2) % mmod;
      if (num == 0) zero_plus[nxt] --; else trans[nxt] = (trans[nxt] * (long long)inv[num]) % mmod;

      num = num2;
      prv = nxt;
    }
  }

  int res = 0;
  int pp = 1;
  int zero = 0;
  for (int i=1; i<=max_n; i++) {
    pp = (pp * (long long)trans[i]) % mmod;
    zero += zero_plus[i];
    if (zero) continue;

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

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3