Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

One of your friends desperately needs your help. He is working with a secret agency and doing some encoding stuffs. As the mission is confidential he does not tell you much about that, he just want you to help him with a special property of a number. This property can be expressed as a function f (n) for a positive integer n. It is defined as:

In other words, he needs the sum of all possible pairs whose least common multiple is n. (The least common multiple (LCM) of two numbers p and q is the lowest positive integer which can be perfectly divided by both p and q). For example, there are 5 different pairs having their LCM equal to 6 as (1, 6), (2, 6), (2, 3), (3, 6), (6, 6). So f (6) is calculated as f (6) = (1 + 6) + (2 + 6) + (2 + 3) + (3 + 6) + (6 + 6) = 7 + 8 + 5 + 9 + 12 = 41.

Your friend knows you are good at solving this kind of problems, so he asked you to lend a hand. He also does not want to disturb you much, so to assist you he has factorized the number. He thinks it may help you.

Input 

The first line of input will contain the number of test cases T (T500). After that there will be T test cases. Each of the test cases will start with a positive number C (C15) denoting the number of prime factors of n. Then there will be C lines each containing two numbers P_i and a_i denoting the prime factor and its power (P_i is a prime between 2 and 1000) and ( 1a_i50). All the primes for an input case will be distinct.

Output 

For each of the test cases produce one line of output denoting the case number and f (n) modulo 1000000007. See the output for sample input forexact formatting.

Sample Input 

3
2
2 1
3 1
2
2 2
3 1
1
5 1

Sample Output 

Case 1: 41
Case 2: 117
Case 3: 16

---

觀察一下，
單純每個 sigma 數字被計算到的次數。
分兩類：1) 不具有高次的數字 2) 具有高次的數字

1) 數字 number < N，只會被計算到一次，因為一定是 (number, N)

2) 數字 number 能搭配的次數，是具有高次的次方連乘積，不具有高次的則會出現在另一個數字身上。

最後答案是
sum = (1 + p1 + p1^2 + ... + p1^(num1-1) + (num1+1)*p1^num1)*
(1 + p2 + p2^2 + ... + p2^(num2-1) + (num2+1)*p2^num2)* ... *
(1 + pi + pi^2 + ... + pi^(numi-1) + (numi+1)*pi^numi) + N;

#include <stdio.h>
#define mod 1000000007LL
int main() {
    int testcase;
    int cases, n, i, j;
    long long pi, ai, ans;
    scanf("%d", &testcase);
    cases = 0;
    while(testcase--) {
        scanf("%d", &n);
        ans = 1;
        long long N = 1;
        for(i = 0; i < n; i++) {
            scanf("%lld %lld", &pi, &ai);
            long long tmp = 1, sum = 0;
            for(j = 0; j < ai; j++) {
                sum += tmp;
                sum %= mod;
                tmp = tmp*pi;
                tmp %= mod;
            }
            N *= tmp;
            N %= mod;
            tmp = tmp*(ai+1);
            tmp %= mod;
            sum = (sum+tmp)%mod;
            ans *= sum;
            ans %= mod;
        }
        printf("Case %d: %lld\n", ++cases, (ans+N)%mod);
    }
    return 0;
}