这篇解题报告比较短，但是题目还是很好的，是一道数学性比较强的题目，对于数学不好的OIer可以学习一下。

题目：
Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。

来源：
HNOI2002
POJ - P1091

题目简述：
求a[ i ]∈[1,m]且a[n]=m的数列使得存在{bn}满足∑a[ i ]b[ i ]=1的方案数。
n≤15，m≤100000000。

关键字：裴蜀定理，容斥原理

算法描述：
根据裴蜀定理，原问题转化为求满足gcd(a[ i ])=1的数列的方案数。
可以想到一种递推的方法：用f[ i ]表示当m=i时的答案，补集转化，则f[ i ]=i^n-f[k](k|i)，这样一共有sqrt(m)个子问题，但是这样做的时间复杂度其实还是O(m)的，只不过除以了一个大常数，还是很容易TLE的。
那么我们换一个角度考虑。我们是要除去gcd≠1的部分，那么这其实是一个容斥问题。将m分解质因数，枚举gcd包含哪些质因子，做一遍容斥原理即可。
顺便说一下，听说这题答案有保证不要高精度，不过poj上没写，所以我还是写了高精度。

总结&收获：
这里递推的时间复杂度不能用调和级数的方法变成O(sqrt(m)logm)。刚开始我觉得直接枚举每个i的约数k是O(m)的，所以就想到枚举k的倍数，因为以前做一些题目的时候将枚举约数改成枚举倍数可以用调和级数的方法证明（n/1+n/2+...+n/n=nlogn）是O(nlogn)的，所以这次也想当然地以为变成了sqrt(m)logn，直到提交发现TLE了才反应过来我又sb了，于是才去思考容斥原理的算法。
总的来说，这道题目还是非常好的，可以练习一下OI方面的一些数学基础。同时也可以从中看出，湖南在02年就出这样的题目了，我的能力和强省还是有很大的差距的。

My Code(递推 - 会TLE)：

/*
Title: PKU1091
Data: 2011-6-5
*/

#include <iostream>
#include <memory.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

#define InputFileName        "XXXXXXX"
#define OutputFileName        "Data.out"

using namespace std;

const int HPLen = 15;

struct THP
{
    long long a[HPLen+1];
}f[30000], g[30000];
int n, m, a[30000], Total;

inline void operator *=(THP &a, const int b)
{
    for (int i = HPLen, r = 0; i; --i)
    {
        a.a[i] = a.a[i]*b+r;
        r = a.a[i]/1000000000;
        a.a[i] %= 1000000000;
    }
}

inline void operator +=(THP &a, const THP &b)
{
    for (int i = HPLen, r = 0; i; --i)
    {
        a.a[i] += b.a[i]+r;
        r = a.a[i]/1000000000;
        a.a[i] %= 1000000000;
    }
}

inline void operator -=(THP &a, const THP &b)
{
    for (int i = HPLen, r = 0; i; --i)
    {
        a.a[i] -= b.a[i]+r;
        if (a.a[i] < 0)
        {
            a.a[i] += 1000000000;
            r = 1;
        }
        else
            r = 0;
    }
}

void Print(const THP &x)
{
    int i = 1;
    for (; i < HPLen && ! x.a[i]; ++i);
    for (printf("%lld", x.a[i++]); i <= HPLen; printf("%09lld", x.a[i++]));
    printf("\n");
}

inline int Lower_Bound(const int k)
{
    int Res = 0;
    for (int l = 1, r = Total, mid = l+r >> 1; l <= r; mid = l+r >> 1)
        a[mid] >= k ? r = (Res = mid)-1 : l = mid+1;
    return Res;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen(InputFileName, "r", stdin);
    freopen(OutputFileName, "w", stdout);
    #endif
    cin >> n >> m;
    f[1].a[HPLen] = 1;
    for (int i = 1; i*i <= m; ++i)
        if (m % i == 0)
        {
            a[++Total] = i;
            if (i*i < m)
                a[++Total] = m/i;
        }
    sort(a+1, a+Total+1);
    g[1].a[HPLen] = 0;
    for (int i = 1, j; i <= Total; ++i)
    {
        f[i].a[HPLen] = 1;
        for (j = 1; j <= n; ++j)
            f[i] *= a[i];
        f[i] -= g[i];
        for (j = a[i]*2; j <= m; j += a[i])
            if (m % j == 0)
                g[Lower_Bound(j)] += f[i];
    }
    Print(f[Lower_Bound(m)]);
    return 0;
}


My Code(容斥)：

/*
Title: PKU1091
Data: 2011-6-5
*/

#include <iostream>
#include <memory.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

#define InputFileName        "XXXXXXX"
#define OutputFileName        "Data.out"

using namespace std;

const int HPLen = 20;

struct THP
{
    long long a[HPLen+1];
}Ans, tmp[100], Minus;
int n, m, a[100], Total, Next[100], Prev[100];

inline void operator *=(THP &a, const int b)
{
    for (int i = HPLen, r = 0; i; --i)
    {
        a.a[i] = a.a[i]*b+r;
        r = a.a[i]/1000000000;
        a.a[i] %= 1000000000;
    }
}

inline void operator +=(THP &a, const THP &b)
{
    for (int i = HPLen, r = 0; i; --i)
    {
        a.a[i] += b.a[i]+r;
        r = a.a[i]/1000000000;
        a.a[i] %= 1000000000;
    }
}

inline void operator -=(THP &a, const THP &b)
{
    for (int i = HPLen, r = 0; i; --i)
    {
        a.a[i] -= b.a[i]+r;
        if (a.a[i] < 0)
        {
            a.a[i] += 1000000000;
            r = 1;
        }
        else
            r = 0;
    }
}

void Print(const THP &x)
{
    int i = 1;
    for (; i < HPLen && ! x.a[i]; ++i);
    for (printf("%lld", x.a[i++]); i <= HPLen; printf("%09lld", x.a[i++]));
    printf("\n");
}

void DFS(const int h, int s, int i)
{
    int j;
    for (; i <= Total; i = Next[i])
    {
        s *= a[i];
        memset(&tmp[h], 0, sizeof(THP));
        tmp[h].a[HPLen] = 1;
        for (j = 1; j <= n; ++j)
            tmp[h] *= m/s;
        if (h & 1)
            Minus += tmp[h];
        else
            Ans += tmp[h];
        Prev[Next[i]] = Prev[i];
        Next[Prev[i]] = Next[i];
        DFS(h+1, s, Next[i]);
        Prev[Next[i]] = Next[Prev[i]] = i;
        s /= a[i];
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen(InputFileName, "r", stdin);
    freopen(OutputFileName, "w", stdout);
    #endif
    cin >> n >> m;
    int k = m;
    for (int i = 2; i*i <= k; ++i)
        if (k % i == 0)
        {
            a[++Total] = i;
            for (; k % i == 0; k /= i);
        }
    if (k > 1)
        a[++Total] = k;
    for (int i = 0; i <= Total; ++i)
        Prev[Next[i] = i+1] = i;
    Ans.a[HPLen] = 1;
    for (int i = 1; i <= n; ++i)
        Ans *= m;
    DFS(1, 1, 1);
    Ans -= Minus;
    Print(Ans);
    return 0;
}