JS's Blog
0%

POJ 1091 - 跳蚤 （容斥）

Posted on Edited on In ,

题目链接：
http://poj.org/problem?id=1091

题目大意：
给定N,M，有N+1个数字，最后一个必定为M，前面的数字小于等于M，跳蚤可以选择一个数字向左跳该长度，也可以向右，多次选择之后求跳蚤可以跳至左边一单位距离的位置的所有数字组合种数

分析：
顺序考虑很难想，不妨逆向思考，什么情况下跳蚤问题无解，这种问题一般很多地方都有涉及，比如换零钱，凑整之类，总之是在gcd(a1,a2,…,an)≠1gcd(a_1,a_2,\dots,a_n)\not= 1时，问题无解，所以枚举所有可以使N+1个数字不互质的可能情况种数，最后答案用mn−ansm^n-ans即可

实际上数据太水了，不然肯定是要开高精度的，光mnm^n就爆long longlong\space long了

代码：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

int n,m;
int factor[10000],cnt;
int pr[10000];


ll quickpow(ll a,ll n)
{
    ll res = 1;
    while (n)
    {
        if (n&1)    res = res*a;
        a = a *a;
        n >>= 1;
    }
    return res;
}


void factorfind(int x)
{
    cnt = 0;
    for (int i = 2 ; i * i <= x ; i ++)
    {
        if (x%i==0)
        {
            factor[++cnt] = i;
            while (x%i==0)
                x /= i;
        }
    }
    if (x!=1)
        factor[++cnt] = x;
    return;
}

ll dfs(int now,int all,int pos)
{
    if (now==all)
    {
        int x = m;
        for (int i = 1; i <= all ; i ++)
            x /= pr[i];
        return quickpow(x,n);
    }
    ll res = 0;
    for (int i = pos ; i <= cnt; i ++)
    {
        pr[now+1] = factor[i];
        res += dfs(now+1,all,i+1);

    }
    return res;
}



ll solve(int t)
{
    return dfs(0,t,1);
}





int main(){



    while (~scanf("%d%d",&n,&m))
    {
        factorfind(m);
        ll ans = 0;
        for (int i = 1 ; i <= cnt ; i ++)
        {
            ll temp = solve(i);

            if (i&1)    ans += temp;
            else    ans -= temp;
        }
        ans = quickpow(m,n)-ans;
        printf("%lld\n",ans);

    }
    return 0;
}