Just Make A Wish

If you are given two sides of a rectangle, you can find the area of the rectangle very easily. But can you do the opposite? Given the area of a rectangle can you tell me how many different rectangles can have this area, provided the sides of the rectangles must be integer? Two rectangles are equal only if the sides are same. You cannot rotate a rectangle. So if the area is 6 there are 4 different rectangles are possible. They are 1x6, 2x3, 3x2 and 6x1.

This problem is very easy and I am sure you can solve it in a minute. Your problem is much tougher. One of your friends Po has got a magic Genie. Every day the Genie grants Po a wish. When asked to grant the wish, the Genie (depending on its mood) tells a number. If it's positive then Po's land gets multiplied by that number. If it's negative then Po's land is divided by the absolute value of that number. So every day, Po tells you the area of the land Po owns. You need to find out how many different rectangles can have that area. And then output the summation after D days. Initially the area of land Po owns is 1.

Input 

First line of input consists of an integer, T (T10), the number of test cases. Each case starts with an integer, D ( 0 < D10⁶), the number of days this wish granting will go on. Next D lines each has an integer G ( 0 < | G|10⁶), the number with which Po's lands area will be multiplied or divided. If G is negative, it will be a divisor of Po's land area.

Output 

For each case print one line `Case X:' where X is the case number. Then for each wish of a day, find the number of different of rectangles you can make which will have the same area as Po's land and output the summation after D days. As this can be much bigger, output modulo 1000000007 (10⁹ + 7).

Sample Explanation:

1st day: Area = 12 6 ways.

2nd day: Area = 36 9 ways.

3 day: Area= 18 6 ways.

4 day: Area = 90 12 ways.

5 day: Area = 15 4 ways.

So in total (6+9+6+12+4) = 37 ways.

Sample Input 

1
5
12
3
-2
5
-6

Sample Output 

Case 1: 37

Problemsetter: Hasnain Heickal
Special Thanks: Tasnim Imran Sunny

---

題目描述：
依序將數字乘上一個數，或者除一個數，計算每個階段的因數個數的總和。

題目解法：
記住一點，由於數字高達一百萬個，有可能因數個數會超過 int32, 甚至 int64,
因此想要保存原本的數字是不可能的，從因數個數的計算，可以保留質因數的次方即可，

但是每次都跑乘法計算每個(質因數次方+1)的乘積，最慘一次要跑 O(80000) // 100萬內的質數個數

又因為因數個數會超過 int32, int64, 利用 mod 1000000007(質數), 觀察到
保留上一次的因數個數 n, 而倘若某個質因數的次方改變從 a -> b,
那麼會將 n/(a+1)*(b+1)，在 mod 質數的情況下，除一個數字相當於乘上它的反元素。

這裡利用費馬小定理 a^(p-1) ≡ 1 (mod p) // 其中 p 是大於 2 的質數
因此 a^(p-2) 即是 a 的反元素(a * a^(p-1) ≡ 1 mod p)

#include <stdio.h>
#include <string.h>
#define mod 1000000007
#define maxL (1000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int pfactor[1000005], pfactorn[1000005], next[1000005];
int mapped[1000005], count[80000];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    int pt = 0;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            mapped[i] = pt;
            pt++;
            for(k = n/i, j = i*k; k >= i; k--, j -= i) {
                pfactor[j] = i;
                SET(j);
            }
            pfactor[i] = i;
        }
    }
    for(i = 2; i <= n; i++) {
        j = i, k = pfactor[i];
        while(j%k == 0)
            pfactorn[i]++, j /= k;
        next[i] = j;
    }
}
long long mpow(long long x, long long y, long long MOD) {
    if(y == 0)  return 1;
    if(y&1)
        return (x*mpow((x*x)%mod, y>>1, MOD))%MOD;
    return mpow((x*x)%MOD, y>>1, MOD);
}
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    sieve();
    int testcase, cases = 0, n, D;
    ReadInt(&testcase);
    //scanf("%d", &testcase);
    while(testcase--) {
        ReadInt(&n);
        //scanf("%d", &n);
        long long ret = 1, sum = 0;
        int neg;
        memset(count, 0, sizeof(count));
        while(n--) {
            ReadInt(&D);
            //scanf("%d", &D);
            if(D < 0)   neg = 1, D = -D;
            else        neg = 0;
            while(D > 1) {
               // printf("%d ^ %d\n", pfactor[D], pfactorn[D]);
                int &v = count[mapped[pfactor[D]]];
                ret = (ret * mpow(v+1, mod-2, mod))%mod;
                if(neg) v -= pfactorn[D];
                else    v += pfactorn[D];
                ret = (ret * (v+1))%mod;
                D = next[D];
            }
            sum = sum + ret;
            if(sum >= mod)  sum -= mod;
        }
        printf("Case %d: %lld\n", ++cases, sum);
    }
    return 0;
}