KIDx的解题报告
?
题目链接:http://poj.org/problem?id=1091
?
假设卡片上标号分别是a1, a2, ..., an, M,跳蚤跳对应号的次数分别为x1, x2, ..., xn,跳M个单位长度的次数是xn+1,那么要满足已知条件只需满足方程:
a1x1+a2x2+...+anxn+Mxn+1 = 1 有解,即:
gcd (a1, a2, ..., an, M) = 1,接下来对M进行素因子分解,然后排除公因子非1的情况即可。
?
如代码所示:
设g为公因子非1的情况数,f(i)表示有i个公因子的情况数,由容斥原理得:g = f(1) - f(2) + f(3) -... f(k)
?
#include <iostream> using namespace std; #define LL __int64 int fac[35], k, a[20], n, m, x; LL tp; LL my_pow (LL a, int b) //计算a^b { LL res = 1; while (b--) res *= a; return res; } void dfs (int pos, int cnt, int num) //dfs得到卡片中n+1个数有num个公因子时的方法数 { if (cnt == num) { x = m; for (int i = 0; i < cnt; i++) x /= a[i]; //x/p表示[1,x]中有多少个数是p的倍数 tp += my_pow (x, n); //要选n个数,每个数有x种选择 return ; } for (int i = pos; i < k; i++) { a[cnt] = fac[i]; dfs (i+1, cnt+1, num); } } void divide (int p) //分解素因子,fac存放p的所有素因子 { for (int i = 2; i * i <= p; i++) { if (p % i == 0) { fac[k++] = i; p /= i; while (p % i == 0) p /= i; } } if (p > 1) fac[k++] = p; } int main() { LL ans, g; int i; while (cin >> n >> m) { g = 0; divide (m); for (i = 1; i <= k; i++) //g = f(1)-f(2)+f(3)-f(4)+...f(k) { tp = 0; dfs (0, 0, i); if (i & 1) g += tp; else g -= tp; } ans = my_pow (m, n) - g; //ans = m^n - g cout << ans << endl; } return 0; }
?