scturtle's 渣代码集散地

Burnside引理:

设置换群作用于有限集合上，则在G作用下的等价类的数目为：

其中(g)为g在上的不动点个数，即满足g(a)=a的个数。

 Polya定理:

设G是p个对象的一个置换群，用k种颜色涂染这p个对象，在置换群作用下的不同的染色方案数为

其中m(f)为置换f的循环节数。

 欧拉函数的概率解释:

1/p看做从1~n中某数有n的因子p的概率,则1-1/p是没有因子p的概率,最前面的n是指1~n的数的个数,由乘法公式可见F的意义

此题设函数F(n,m)为公因子为1的排列的个数,易见当m为质数时 

普遍看,总排列个数为,取p|m,则1/p为1~m的某数有因子p的概率,为前n个数都有p因子的概率,即这n+1个数有公因子p的概率

所以由乘法公式见:

恩,我理解的大概就是这个样子了...

因为有性质

  当时

所以gcd是积性函数

因为积性函数的和函数也是积性函数(《初等数论及其应用》P182),所以所求函数

是积性函数

问题简化到素数阶段,须求,此时用到欧拉公式.因为有

(易见因为代表的是从1到N中和N最大公约数gcd为d的数的个数)

所以,又因为则可求出

#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned long long u64;
#define maxn 50000
u64 primet[maxn];
int pnum = 0;
void getprimtable()//筛法求出素数
{
    bool flag[maxn] = {false};
    for (long i = 2; i < maxn; i++)
    {
        if (!flag[i])
        {
            primet[pnum++] = i;
            for (long j = i + i; j < maxn; j += i) flag[j] = true;
        }
    }
}

u64 eularpk(u64 p, int k)//欧拉求p^k
{
    if (k == 0) return 1;
    u64 ans = p - 1;
    while (--k)
    {
        ans *= p;
    }
    return ans;
}

u64 fpk(u64 p, int k)//求f(p^k)
{
    u64 ans = 0, t = 1;
    for (int i = 0; i <= k; i++)
    {
        ans += t * eularpk(p, k - i);
        t *= p;
    }
    return ans;
}

u64 f(u64 n)//求f 因式分解
{
    u64 sum = 1;
    int p, k;
    for (int i = 0; primet[i]*primet[i] <= n; i++)
    {
        p = primet[i];
        //cout<<p<<ends;
        if (n % p == 0)
        {
            k = 0;
            while (n % p == 0) {n /= p; k++;}
            sum *= fpk(p, k);
        }
    }
    if (n > 1) sum *= fpk(n, 1); // 分解到最后剩下一个素因子
    return sum;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    getprimtable();
    u64 n;
    while (cin >> n)
    {
        cout << f(n) << endl;
    }
}

不互质的中国剩余定理,依次合并!

假设C ≡ A₁ (mod B₁)，C ≡ A₂ (mod B₂)。令C = A₁ + X₁B，那么X₁B₁ ≡ A₂ − A₁ (mod B₂)。用扩展欧几里德算法求出X₁，也就求出C。令B = lcm(B₁, B₂)，那么上面两条方程就可以被C’ ≡ C (mod B)代替。迭代直到只剩下一条方程。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
__int64 x, y, t;
__int64 egcd(__int64 a, __int64 b)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    else
    {
        __int64 e = egcd(b, a % b);
        t = x; x = y; y = t - a / b * y;
        return e;
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    __int64 m1, m2, r1, r2, d, c, t;
    bool sb;
    int n;
    while (cin >> n)
    {
        sb = 0;
        cin >> m1 >> r1;
        for (int i = 0; i < n - 1; i++)
        {
            cin >> m2 >> r2;
            if (sb) continue;
            d = egcd(m1, m2);
            c = r2 - r1;
            if (c % d)
            {
                sb = 1;
                continue;
            }
            t = m2 / d;
            x = (c / d * x % t + t) % t;

            r1 = m1 * x + r1;
            m1 = m1 * m2 / d;
        }
        if (sb)
            cout << -1 << endl;
        else
            cout << r1 << endl;
    }

}

"把组合问题的加法法则和幂级数的t的乘幂的相加对应起来"

"母函数的思想很简单—就是把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造. "

代码基本是这个样子的:

hdoj 1028 整数拆分

#include <iostream>
#include <cstdio>
using namespace std;
#define maxl 300
int ans[maxl+1], t[maxl+1];

int main()
{
    freopen("in.txt", "r", stdin);
    int n, i, j, k;
    while (cin >> n)
    {
        for (i = 0; i <= n; i++)
        {
            ans[i] = 1; t[i] = 0;
        }
        for (i = 2; i <= n; i++)
        {
            for (j = 0; j <= n; j++)
                for (k = 0; k + j <= n; k += i)
                {
                    t[j+k] += ans[j];
                }
            for (j = 0; j <= n; j++)
            {
                ans[j] = t[j]; t[j] = 0;
            }
        }
        cout << ans[n] << endl;
    }
}