【Foreign】光 [莫比乌斯反演]

光

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。

　　

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<bitset>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int MOD = 1e9 + ;

 const int Niyu = ;

 s64 A, B, D;

 int P[ONE],num;

 int vis[ONE];

 s64 Ans;

 int get()

 {

         int res=,Q=;char c;

         while( (c=getchar())< || c> )

         if(c=='-')Q=-;

         res=c-;

         while( (c=getchar())>= && c<= )

         res=res*+c-;

         return res*Q;

 }

 void Factor(int x)

 {

         for(int i=; i*i<=x; i++)

         if(x % i == )

         {

             P[++num] = i;

             while(x % i == ) x /= i;

         }

         if(x != ) P[++num] = x;

 }

 int Calc(int n)

 {

         return (s64)n * (n+) % MOD * (*n+) % MOD * Niyu % MOD;

 }

 void Deal()

 {

         int d = , N = ;

         for(int i=; i<=num; i++)

             if(vis[i]) d = (s64)d * P[i] % MOD ,N++;

         N = N &  ? MOD- : ;

         Ans = Ans + (s64)N % MOD * d % MOD * d % MOD * Calc((D+) / d) % MOD,

         Ans %= MOD;

 }

 void Dfs(int T)

 {

         if(T > num) {Deal(); return;}

         vis[T] = ; Dfs(T+);

         vis[T] = ; Dfs(T+);

 }

 int main()

 {

         cin>>A>>B>>D;

         if(D & ) {printf(""); return ;}

         Factor(D + );

         Dfs();

         printf("%d", (s64)(A * A % MOD + B * B % MOD) % MOD * Ans % MOD);

 }