首页 > 代码库 > 【Foreign】光 [莫比乌斯反演]
【Foreign】光 [莫比乌斯反演]
光
Time Limit: 10 Sec Memory Limit: 128 MBDescription
天猫有一个长方形盒子，长宽分别为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
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<bitset> 9 using namespace std; 10 typedef long long s64;11 12 const int ONE = 50005;13 const int MOD = 1e9 + 7;14 const int Niyu = 166666668;15 16 s64 A, B, D;17 int P[ONE],num;18 int vis[ONE];19 s64 Ans;20 21 int get()22 { 23 int res=1,Q=1;char c; 24 while( (c=getchar())<48 || c>57 ) 25 if(c==‘-‘)Q=-1; 26 res=c-48; 27 while( (c=getchar())>=48 && c<=57 ) 28 res=res*10+c-48; 29 return res*Q;30 }31 32 void Factor(int x)33 {34 for(int i=2; i*i<=x; i++)35 if(x % i == 0)36 {37 P[++num] = i;38 while(x % i == 0) x /= i;39 }40 if(x != 1) P[++num] = x;41 }42 43 int Calc(int n)44 {45 return (s64)n * (n+1) % MOD * (2*n+1) % MOD * Niyu % MOD; 46 }47 48 void Deal()49 {50 int d = 1, N = 0;51 for(int i=1; i<=num; i++)52 if(vis[i]) d = (s64)d * P[i] % MOD ,N++;53 N = N & 1 ? MOD-1 : 1;54 Ans = Ans + (s64)N % MOD * d % MOD * d % MOD * Calc((D+2) / d) % MOD,55 Ans %= MOD; 56 }57 58 void Dfs(int T)59 {60 if(T > num) {Deal(); return;}61 vis[T] = 1; Dfs(T+1);62 vis[T] = 0; Dfs(T+1);63 }64 65 int main()66 {67 cin>>A>>B>>D;68 if(D & 1) {printf("0"); return 0;}69 Factor(D + 2);70 Dfs(1);71 printf("%d", (s64)(A * A % MOD + B * B % MOD) % MOD * Ans % MOD);72 }
【Foreign】光 [莫比乌斯反演]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。