594d_fastin.go

package main

import "fmt"
import "sort"
import "os"
import "bufio"
import "strconv"

type B struct {
  l, r, id int
}

type Bs []B

func (s Bs) Len() int {
  return len(s)
}

func (s Bs) Swap(i, j int){
  s[i], s[j] = s[j], s[i]
}

func (s Bs) Less(i, j int) bool { return s[i].r < s[j].r }

var scanner *bufio.Scanner

func main() {
  scanner = bufio.NewScanner(os.Stdin)
  scanner.Split(bufio.ScanWords)

  for i := 2; i<MAX; i++ {
    if (0==fac[i]) {
      for j := i; j < MAX; j += i {
        fac[j] = i;
      }
    }
  }

  n := ri()
  for i := 0; i<n; i++ {
    a[i] = ri();
    if i!=0 {
      prod[i] = int(int64(prod[i-1]) * int64(a[i]) % MOD)
    } else {
      prod[i] = int(int64(a[i]) % MOD)
    }
  }
  q := ri()
  for i:=0; i<q; i++ {
    b[i].id = i;
    b[i].l = ri()-1;
    b[i].r = ri()-1;
  }

  //sort!("a.r < b.r")(b[0..q]); // TODO
  sort.Sort(Bs(b[0:q]))

  for i:=0; i<NN*2; i++ {
    seg[i] = 1;
  }

  j := 0;
  for i:=0; i<n; i++ {
    for x := a[i]; x > 1; {
      y := fac[x];
      x /= y
      for (x % y == 0){x /= y}
      modify(pre[y], i+1, int(int64(y-1)*int64(inv(y))%MOD));
      pre[y] = i+1;
    }

    for ; j < q && b[j].r == i; j++ {
      if b[j].l != 0 {
        ans[b[j].id] = int(int64(query(b[j].l)) * int64(prod[i]) % MOD * int64(inv(prod[b[j].l-1])) % MOD);
      } else {
        ans[b[j].id] = int(int64(query(b[j].l)) * int64(prod[i]) % MOD % MOD);
      }
    }
  }
  for i:=0; i<q; i++ {
    fmt.Printf("%d\n", ans[i]);
  }
}

func ri1() int {
  var x int;
  fmt.Scanf("%d", &x);
  return x;
}

func ri() int {
  scanner.Scan()
  x, _ := strconv.Atoi(scanner.Text())
  return x
}

const N = 200000
const NN = 1 << 18
const Q = 200000
const MAX = 1000001
const MOD = 1000000007;

var b [Q]B;

var pre [MAX]int
var fac [MAX]int
var a [N]int
var prod [N]int
var seg [NN*2]int
var ans [Q]int

func modify(l, r, x int) {
  l += NN-1
  r += NN-1
  for ; l < r; {
    if (l%2 == 0) {
      seg[l] = int(int64(seg[l]) * int64(x) % MOD);
    }
    if (r%2 == 0) {
      r--;
      seg[r] = int(int64(seg[r]) * int64(x) % MOD);
    }
    l >>= 1;
    r >>= 1;
  }
}

func query(i int) int {
  r := 1;
  for i += NN-1; ; {
    r = int(int64(r) * int64(seg[i]) % MOD);
    if (i==0) {break;}
    i = ((i-1) >> 1);
  }
  return r;
}

func inv(x int) int {
  r := 1;
  for ; x > 1; x = MOD % x {
    r = int(int64(r) * int64(-MOD/x) % MOD)
  }
  return (r+MOD)%MOD;
}