2013年8月31日

UVa 12619 - Just Make A Wish

Referecne : http://mypaper.pchome.com.tw/zerojudge/post/1324552689
#include <cstdio>

typedef unsigned long long ULL;
const ULL MOD = 1000000007;
const int SIZE = 1000000 + 1;

bool notP[SIZE];
int indexOfP[SIZE], p[SIZE / 10], N;

ULL power(ULL n, ULL e) {
  if (!e) {
    return 1;
  }
  return (((e & 1) ? n : 1) * (power((n * n) % MOD, e >> 1))) % MOD;
}

int main() {
  notP[0] = notP[1] = true;
  for (int i = 2; i < SIZE; i++) {
    if (!notP[i]) {
      p[N] = i;
      indexOfP[i] = N++;
      for (int j = i + i; j < SIZE; j += i) {
        notP[j] = true;
      }
    }
  }
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int D;
    scanf("%d", &D);
    ULL times[SIZE / 10] = {}, ans = 0, sum = 1;
    while (D--) {
      int G;
      bool minus = false;
      scanf("%d", &G);
      if (G < 0) {
        G = -G;
        minus = true;
      }
      for (int j = 0; j < N && notP[G] && G >= p[j]; j++) {
        ULL time = 0;
        while (!(G % p[j])) {
          G /= p[j];
          time++;
        }
        if (time) {
          sum = (sum * power(times[j] + 1, MOD - 2)) % MOD;
          times[j] += time * (minus ? -1 : 1);
          sum = (sum * (times[j] + 1)) % MOD;
        }
      }
      if (!notP[G]) {
        int j = indexOfP[G];
        ULL temp = times[j];
        sum = (sum * power(times[j] + 1, MOD - 2)) % MOD;
        times[j] += minus ? -1 : 1;
        sum = (sum * (times[j] + 1)) % MOD;

      }
      ans = (ans + sum) % MOD;
    }
    printf("Case %d: %llu\n", C++, ans);
  }

  return 0;
}

沒有留言:

張貼留言