光

Time Limit: 10 Sec Memory Limit: 128 MB

Description

天猫有一个长方形盒子，长宽分别为A，B。
　　这个长方形盒子的内壁全部是镜面。
　　天猫在这个盒子的左下方放了一个激光灯。
　　这个灯可以照向盒子内的任意角度。
　　现在天猫想要打开这个激光灯，但是他想让光线按照如下规则照射：
　　　　1.这束光必须恰好打到盒子边缘反射D次，并且不能碰到任意一个角落（除了出发点以及结束点）。
　　　　2.这束光必须到达盒子右上角，并且结束反射。
　　天猫想要知道，所有合法的光线路线的长度平方和是多少。
　　作为一个资深OIer，你应该知道输出要对10^9+7取模。

Input

一行三个数，表示A、B、D。

Output

一个数，表示路径平方和。

Sample Input

3 3 2

Sample Output

180

HINT

D<=10^9, A,B<=10^6

Solution

首先，我们注意到若一束光在一个平面反射，相当于镜面一侧的物体对称到镜面另一侧，而光线穿过镜面照到物体成的虚像上。
　　所以，我们可以认为：有一个D∗D的网格，需要在这个网格上面找到一点**(x,y)，要满足x+y−2 = D**，这样的话，我们把**(0,0)与(x,y)连接起来，连线所经过的网格边就是镜面反射时经过的边**。也就是说，任意的合法方案与整数对(x,y)是一一对应的。
　　注意，由于在反射过程中，不能碰到网格的角落，所以应该满足**(0,0)与(x,y)连线上没有其他整点**，也就是gcd(x,y)=1，即gcd(x,D+2)=1。

然后用莫比乌斯反演推一波式子，最后发现要用暴力解决qaq。

img

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 50005;
const int MOD = 1e9 + 7;
const int Niyu = 166666668;

s64 A, B, D;
int P[ONE],num;
int vis[ONE];
s64 Ans;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Factor(int x)
{
    for(int i=2; i*i<=x; i++)
        if(x % i == 0)
        {
            P[++num] = i;
            while(x % i == 0) x /= i;
        }
    if(x != 1) P[++num] = x;
}

int Calc(int n)
{
    return (s64)n * (n+1) % MOD * (2*n+1) % MOD * Niyu % MOD;
}

void Deal()
{
    int d = 1, N = 0;
    for(int i=1; i<=num; i++)
        if(vis[i]) d = (s64)d * P[i] % MOD ,N++;
    N = N & 1 ? MOD-1 : 1;
    Ans = Ans + (s64)N % MOD * d % MOD * d % MOD * Calc((D+2) / d) % MOD,
    Ans %= MOD;
}

void Dfs(int T)
{
    if(T > num) {Deal(); return;}
    vis[T] = 1; Dfs(T+1);
    vis[T] = 0; Dfs(T+1);
}

int main()
{
    cin>>A>>B>>D;
    if(D & 1) {printf("0"); return 0;}
    Factor(D + 2);
    Dfs(1);
    printf("%d", (s64)(A * A % MOD + B * B % MOD) % MOD * Ans % MOD);
}