POJ1091跳蚤（容斥 + 唯一分解 + 快速幂）

题意：规定每次跳的单位 a1, a2, a3 …… , an, M，次数可以为b1, b2, b3 …… bn, bn + 1, 正好表示往左，负号表示往右，求能否调到左边一位，即 a1* b1+ a2 * b2 + a3 * b3 + …… + m * (bn + 1) = 1;

根据欧几里得，则a1, a2 a3 …… an, m 最大公约数为1，m已知且a1, a2, a3 …… an 均小于等于m, 一共有m ^ n可能，将m 唯一分解之后，假设m = 2 * 3 * 5, 则不大于m且包含2因子的共 m / 2, 包含3的为 m/ 3, 容斥

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 const int Max = 10000 + 10;
 7 typedef long long LL;
 8 LL n, m;
 9 int prime[Max + 10], vis[Max + 10], tot;
10 LL em[100], a[100], cnt;
11 LL res;
12 void getPrime()
13 {
14     tot = 0, cnt = 0;
15     memset(vis, 0, sizeof(vis));
16     for (int i = 2; i <= Max; i++)
17     {
18         if (!vis[i])
19         {
20             prime[tot++] = i;
21             for (int j = i; j <= Max / i; j++)
22                 vis[i * j] = 1;
23         }
24     }
25 
26 }
27 void getfactor(int b)
28 {
29     memset(em, 0, sizeof(em));
30     for (int i = 0; i < tot; i++)
31     {
32         if (prime[i] > b)
33             break;
34         if (b % prime[i] == 0)
35         {
36             em[cnt++] = prime[i];
37             while (b % prime[i] == 0)
38             {
39                 b /= prime[i];
40             }
41         }
42     }
43     if (b > 1)
44         em[cnt++] = b;
45 }
46 LL Pow(LL a, LL b)
47 {
48     LL ans = 1;
49     while (b > 0)
50     {
51         if (b & 1)
52             ans *= a;
53         b >>= 1;
54         a *= a;
55     }
56     return ans;
57 }
58 void dfs(int cur, int num, int Cnt)  // cur当前位置， num当前已包含个数，Cnt目标个数
59 {
60     if (num == Cnt)
61     {
62 //达到目标个数时， 用 m 去除以 所有包含的数
63         LL u = m;
64         for (int i = 0; i < num; i++)
65             u /= a[i];
66         res += Pow(u, n);
67         return;
68     }
69     for (int i = cur; i < cnt; i++)
70     {
71         a[num] = em[i];
72         dfs(i + 1, num + 1, Cnt);
73     }
74     return;
75 }
76 int main()
77 {
78     getPrime();
79     while (scanf("%I64d%I64d", &n, &m) != EOF)
80     {
81         getfactor(m);
82         LL sum = Pow(m, n);
83         for (int i = 1; i <= cnt; i++) // 枚举每一个组合，i表示每个组合中数的个数
84         {
85             res = 0;
86             dfs(0, 0, i);
87             if (i & 1)
88                 sum -= res;
89             else
90                 sum += res;
91         }
92         printf("%I64d
", sum);
93     }
94 
95     return 0;
96 }

View Code

POJ1091跳蚤（容斥 + 唯一分解 + 快速幂）

相关推荐