关于Dijkstra算法

2010年7月21日 没有评论

其实Dijkstra算法只是基于以下显而易见的事实：

所有未知的路径都是由已知路径生成的，当然我们找到其中最小的那条（也许不止一条^^）。
如果所有边的权都是正的(这也是有负权Dijkstra失效的原因)，那么显然，新生成的路径的权值都不会比原来的小。
那么显然所有生成的路径都不会小于原来最小的那几条，这些路径显然就是最短路^^。
显然的，我们不需要关注那些不会再生成新路径的点，接着我们把刚才找到的这个点也变成这种类型的（这个好办，把它能生成的直接路径都生成了），接着，情况又和刚才一致了^^

考虑初始情况，就是我们第一次出发的那个点，到达这个点的权值显然是0，接着从它出发生成它能直接产生的新路径（就是和它直接连着的点），然后again and again...

分类: ACM 标签:

循环节

2010年6月1日 2 条评论

记得以前我之前写过一篇分数循环节相关的文章，今天扩展一下：讨论下分数的循环解和指数mod p的循环节

考虑a/m在p进制下的输出（gcd(a,m)=1）和f(n)的循环节.首先说一下前者，因为前者的循环可以由后者直接得到！两者是同步的！当然有一种方式能使你很快意识到这一点

给出以下描述，如果t是使gcd(p^{t-1},m)最大的最小正整数,那么t就是循环起始的位置。简单的说，从t开始，\forall{n}\in{N^*},n\geqslant{t},g=gcd(p^{t-1},m)都不再变化(这个g后面会用到)。

显然当n小于t时gcd(f(n),m)和n大于等于t时的gcd(f(n),m)不同,所以n小于t时的f(n)不可能和后面的n大于等于t时的f(n)的任何一个相等，t之前的n就不会出现在循环内！当然，这还不能证明t就在循环内

当然由欧拉定理，我们可以马上得到，当gcd(p,m)=1时，循环节存在（欧拉函数的值必为循环节的倍数），且必然是从n=1开始的

然后注意到以下事实：

于是f(n)=g\cdot (\frac {a \cdot p^{n-1}}{g}\;\; mod \;\frac{m}{g}) \;,n \geqslant t此时gcd(p^{n-1} , \frac{m}{g})=1，这和gcd(p,m)=1的情况其实是同构的.

令a= \frac{a \cdot p^{t-1}}{g},m= \frac{m}{g},n=n-t，你就得到了和初始的式子一样的一个新式，用上面的欧拉定理你可以证明这次的这个是循环的，因为gcd(p,m)=1了，最后，别忘了这个是从第t位开始的（因为有变换n=n-t），而且结果需要乘以g（因为之前把这个公约数给提出来了）。

这个循环可以一一映射到分数的循环节，如果你把那个小学就学过了的竖式想得够彻底的话，这一切都是显然的

分类: Math 标签:

基于2进制的大数类

2010年5月25日 1 条评论

我写的另一个大数类，基于二进制（确切的说在32位机下是2^31次进制），乘法是用移位和加法模拟的（如果不是考虑到64位兼容性的话，用long long可以显著提高乘法效率），除法是移位和减法（状况同乘法），效率上比我原来的那个低了很多（有兴趣的可以看我之前的文章，基于10^9次进制的大数类），尤其是输出函数。但毕竟是是我精心设计的，很多方面感觉还是很有价值的

有需要的朋友可以下载我的源码（基于code::blocks的工程）

下面是其中的一个头文件，包括了大数类的主要声明

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

#ifndef LARGEINT_H_INCLUDED
#define LARGEINT_H_INCLUDED
 
#include "numarray.h"
 
const int bits=8*sizeof(numunit)-1;         //每一个存储单位的2进制位数
const int intlim=1000000000;//numunit能够容纳的最大的10的幂
const int intlimbits=9;//上面那个intLim的十进制位数（幂）
 
class largeInt
{
private:
    numArray number;     //反序保存数剧本身，最低位是number[0]
    int length;          //number的长度
    int sign;            //符号1表示正，-1表示负数，特殊的,有两个0,保证0的符号是1
public:
    largeInt() {length=1;sign=1;}
    largeInt(int in) {length=1;sign=(in>=0)?1:-1;number[0]=(numunit)sign*in;}
    largeInt(const largeInt &in) {number=in.number;length=in.length;sign=in.sign;}
    largeInt& operator=(const largeInt &in) {number=in.number;length=in.length;sign=in.sign;return *this;}
    largeInt operator-() const {largeInt opposite=(*this);opposite.sign=-sign;return opposite;}
    void opposite() {sign*=-1;}
    //##I/O################################
    largeInt& read();
    largeInt& read(const char *);
    void print() const;
private:
    void printAll(largeInt &num) const;
    void printDecimalUnit(int unit,int len) const;
    void printDecimalUnit(int unit) const;
public:
    //##compare############################
    bool operator==(const largeInt&) const;
    bool operator>(const largeInt&) const;
    bool operator<(const largeInt&) const;
    bool operator>=(const largeInt &right) const {return !(*this<right);}
    bool operator<=(const largeInt &right) const {return !(*this>right);}
    bool operator!=(const largeInt &right) const {return !(*this==right);}
    //##movement###########################
    largeInt operator<<(int n) const {largeInt solution=*this;solution<<=n;return solution;}
    largeInt operator>>(int n) const {largeInt solution=*this;solution>>=n;return solution;}
    const largeInt& operator<<=(int);
    const largeInt& operator>>=(int);
private:
    void moveLeft(int);    //大移位，移1就是移动bits位
    void moveRight(int);
public:
    //##+ - * / %##########################
    largeInt operator++(int) {*this+=1;return *this-1;}//后缀运算
    const largeInt& operator++() {return *this+=1;}//前缀
    largeInt operator--(int) {*this-=1;return *this+1;}
    const largeInt& operator--() {return *this-=1;}
    //*************************************
    largeInt operator+(const largeInt &right) const {largeInt solution=*this;solution+=right;return solution;}
    const largeInt& operator+=(const largeInt&);
    largeInt operator-(const largeInt &right) const {largeInt solution=*this;solution-=right;return solution;}
    const largeInt& operator-=(const largeInt&);
    largeInt operator*(const largeInt&) const;
    largeInt operator*(int) const;
    const largeInt operator*=(const largeInt &right) {return *this=*this*right;}
    const largeInt operator*=(int right) {return *this=*this*right;}
    largeInt operator/(largeInt&) const;
    largeInt operator/(int) const;
    largeInt operator/(const largeInt &divi) const {largeInt divisor=divi;return *this/divisor;}
    const largeInt& operator/=(largeInt &divisor) {return *this=*this/divisor;}
    const largeInt& operator/=(const largeInt &divi) {largeInt divisor=divi;return *this/=divisor;}
    const largeInt& operator/=(int divisor) {return *this=*this/divisor;}
    largeInt operator%(const largeInt &divisor) const {largeInt solution;solution%=divisor;return solution;}
    largeInt operator%(largeInt &divisor) const {largeInt solution;solution%=divisor;return solution;}
    const largeInt& operator%=(largeInt&);
    const largeInt& operator%=(const largeInt &divisor) {largeInt divi=divisor;return *this%=divi;}
    const largeInt& operator%=(int);
    int operator%(int) const;              //特殊的取模函数，用于返回int型的余数
    //**************************************
    friend largeInt operator+(int a,const largeInt& b) {return b+a;}
    friend largeInt operator-(int a,const largeInt& b) {return -(b-a);}
    friend largeInt operator*(int a,const largeInt& b) {return b*a;}
    friend largeInt operator/(int a,const largeInt& b) {largeInt x=a;return a/b;}
    friend largeInt operator%(int a,const largeInt& b) {largeInt x=a;return a%b;}
private:
};
 
 
#endif // LARGEINT_H_INCLUDED
分类: Cpp 标签:

等比序列的前n项和

2010年5月11日 1 条评论

计算等比数列前n项和，首先想到高中学过的公式

这个公式是出色的，而且用逐次平方法就可以算出q^n，当然当n很大的时候，如果我们要对结果取模，那么显然这个公式中出现的除法是很糟糕的（取模运算不能对除法满足分配律），于是，我给出了下面的方法。首先看下面的式子：

你有发现什么吗？有没有看到里面的递推特性？
要知道我特意选了15，因为15的2进制表示中每一位都是1.很遗憾，这个式子我很难用逐次平方法那样显而易见的式子了表示，我只能说，两者是类似的（其实我觉得这已经是显而易见的了）。
我只能在下面的两个式子里，给出了一个基于二进制的标识，式子下面的一串数是二进制的各位，找规律吧

依然给出代码，这是一个O(lgn)的基于递推的算法，和用公式的效率是接近的。和递归的二分类似，但理解更困难

特别的，模p的代码就不加了，当然添加是很简单的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int sum(int q,int n)
{
    int solution=0,temp=1;
    while(n) //n不为0就循环
    {
        if(n%2) //如果n是奇数
        {
            solution*=q;
            solution+=temp; 
        }
        temp*=(1+q);//生成上面式子中数字1所对应的表达式
        q*=q;
        n>>=1;
    }
    return solution;
}
分类: Cpp 标签:

逐次平方法(快速幂取模)

2010年5月11日 没有评论

快速幂取模，方法其实就是逐次平方法.计算a^k mod m:

将k表示成2进制,有

由ur的值决定该因子是否乘入（是就是1，否是0），每一个因子都可以由前一个递推的产生，于是，给出下面的函数(考虑到n会很大，所以对结果取模),时间上是O(lgn)的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int x_Power_k_Mode_m(int x,int k,int m)  //x^k(mod m)
{
    int solution=1;
    x%=m;
    while(k)
    {
        if(k%2)
        {
            solution*=x;
            solution%=m;
        }
        x*=x;
        x%=m;
        k>>=1;
    }
    return solution;
}
分类: Cpp, Math 标签: