STEP BY STEP

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

此题是求一个数字序列中，长度为3的子序列(a,b,c)，且满足条件a<=b<=c或者c<=b<=a的子序列的个数。
明显枚举每个b，求每个b左边的a的个数和右边c的个数，以及左边c的个数和右边a的个数，然后累加左右乘积求和即可。刚开始只求了满足条件a<=b<=c的部分，而且忘记用64位了。wa了几次。求左边a的个数其实就是求小于等于b的数字的个数，这个刚好可以用树状数组或者线段树求。具体见代码。

代码如下：

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;
const INT MAX_N =  100010;
const INT N = 20010;
INT nN;
INT nNum[N];
INT nTree[MAX_N + 10];
INT nLeft[2][N], nRight[2][N];

INT LowBit(INT nI)
{
    return nI  & (-nI);
}

void Add(INT nI, INT nAdd)
{
    while (nI <= MAX_N)
    {
        nTree[nI] += nAdd;
        nI += LowBit(nI);
    }
}

INT Query(INT nPos)
{
    INT nAns = 0;
    while (nPos > 0)
    {
        nAns += nTree[nPos];
        nPos -= LowBit(nPos);
    }
    return nAns;
}

int main()
{
    INT nT;

    scanf("%I64d", &nT);
    while (nT--)
    {
        scanf("%I64d", &nN);
        memset(nTree, 0, sizeof(nTree));
        for (INT i = 1; i <= nN; ++i)
        {
            scanf("%I64d", nNum[i]);
            nLeft[0][i] = Query(nNum[i]);
            nLeft[1][i] = Query(MAX_N) - Query(nNum[i] - 1);
            Add(nNum[i], 1);
        }
        memset(nTree, 0, sizeof(nTree));
        for (INT i = nN; i >= 1; --i)
        {
            nRight[0][i] = Query(MAX_N) - Query(nNum[i] - 1);
            nRight[1][i] = Query(nNum[i]);
            Add(nNum[i], 1);
        }
        INT nAns = 0;
        for (INT i = 1; i <= nN; ++i)
        {
            nAns += nLeft[0][i] * nRight[0][i] + nLeft[1][i] * nRight[1][i];
        }
        printf("%I64d\n", nAns);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

这个题意思是翻转一个01立方体。翻转多次后再查询某个点的值。
还是利用上一篇文章的思想，把翻转操作转换为单点更新操作。把查询操作转换为利用树状数组查询和的方式。这样每次操作的复杂度都是logN的3次。而直接翻转立方体的复杂度是N的3次。
这个题最麻烦的地方是空间想象能力。因为要翻转8个点才能完成一次立方体翻转。比如，翻转(x,y,z)相当于以该点作为左上角做一个无限立方体，把该立方体翻转。这样就会翻转多余的部分，那么需要把多翻转的部分翻转回来。最后的思考结果发现，只要对每个顶点翻转一次即可。至于为什么这样，自己去计算重复翻转的部分就会明白了。刚好确实是把每个点翻转了一次。

代码如下：

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 110;
int nSum[MAX_N + 10][MAX_N + 10][MAX_N + 10];
int nN, nM;

int LowBit(int nPos)
{
    return nPos & (-nPos);
}

void Add(int nX, int nY, int nZ)
{
    for (int i = nX; i <= nN; i += LowBit(i))
    {
        for (int j = nY; j <= nN; j += LowBit(j))
        {
            for (int k = nZ; k <= nN; k += LowBit(k))
            {
                nSum[i][j][k]++;
            }
        }
    }
}

int Query(int nX, int nY, int nZ)
{
    int nAns = 0;

    for (int i = nX; i > 0; i -= LowBit(i))
    {
        for (int j = nY; j > 0; j -= LowBit(j))
        {
            for (int k = nZ; k > 0; k -= LowBit(k))
            {
                nAns += nSum[i][j][k];
            }
        }
    }
    return nAns;
}

int main()
{
    int nCmd;
    int nX, nY, nZ;
    int nX1, nY1, nZ1;
    int nX2, nY2, nZ2;

    while (scanf("%d%d", &nN, &nM) == 2)
    {
        memset(nSum, 0, sizeof(nSum));
        while (nM--)
        {
            scanf("%d", &nCmd);
            if (nCmd == 0)
            {
                scanf("%d%d%d", &nX, &nY, &nZ);
                printf("%d\n", Query(nX, nY, nZ) % 2);
            }
            else
            {
                scanf("%d%d%d%d%d%d", &nX1, &nY1, &nZ1, &nX2, &nY2, &nZ2);
                if (nX1 > nX2)swap(nX1, nX2);
                if (nY1 > nY2)swap(nY1, nY2);
                if (nZ1 > nZ2)swap(nZ1, nZ2);
                Add(nX1, nY1, nZ1);

                Add(nX2 + 1, nY1, nZ1);
                Add(nX1, nY2 + 1, nZ1);
                Add(nX1, nY1, nZ2 + 1);

                Add(nX1, nY2 + 1, nZ2 + 1);
                Add(nX2 + 1, nY1, nZ2 + 1);
                Add(nX2 + 1, nY2 + 1, nZ1);

                Add(nX2 + 1, nY2 + 1, nZ2 + 1);
            }
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

这个题的意思是给定一个长为N的区间。不断的给某个子区间[A,B]中的每个点涂一次色。最后问每个点的涂色次数。
这个题貌似可以扩展到多维的情况，但是多维的情况下必须用树状数组求和以加快速度，一维的情况直接求和即可。
假如，第一次涂色是对区间[A,B]涂色一次，可以让nNum[nA]++,nNum[nB+1]—即可。因为这样对于区间[0,nA-1]的任意值i有都要nNum[1]+nNum[2]+…+nNum[i] = 0。而对于区间[nA,nB]的任意值i有nNum[1]+nNum[2]+…+nNum[i] = 0。对于区间[nB+1, nN]的任意值i有nNum[1]+nNum[2]+…+nNum[i] = 0。那么重复多次了。如果上述求和nNum[1]+nNum[2]+…+nNum[i] 刚好代表每个结点i的涂色次数，那么这个题就可解了。
用例子验证一下，发现肯定是这样的。证明略了。至于树状数组网上一大堆资料。树状数组模板单一，敲代码太方便了。

代码如下：

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int nNum[100000 + 10];
int nN;
int LowBit(int nI)
{
    return nI & (-nI);
}

void Add(int nI, int nAdd)
{
    while (nI <= nN)
    {
        nNum[nI] += nAdd;
        nI += LowBit(nI);
    }
}

int GetSum(int nI)
{
    int nAns = 0;

    while (nI > 0)
    {
        nAns += nNum[nI];
        nI -= LowBit(nI);
    }
    return nAns;
}

int main()
{
    int nA, nB;

    while (scanf("%d", &nN), nN)
    {
        memset(nNum, 0, sizeof(nNum));

        for (int i = 1; i <= nN; ++i)
        {
            scanf("%d%d", nA, nB);
            Add(nA, 1);
            Add(nB + 1, -1);
        }
        for (int i = 1; i <= nN; ++i)
        {
            printf("%d%s", GetSum(i), i == nN ? "\n" : " ");
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

这个题是求次短路。有个不错的解法，是根据一个结论，替换调最短路里面的一条边肯定能得到次短路。
那么，只要枚举所有边就可以了。比如，假设开始点为s，目标点是d，设最短路为dis(s,d)。对于边(u,v)，dis(s, u) + w(u, v) + dis(v, d) 大于dis(s, d)，则该路径就可能是次短路。求出最小的大于dis(s,d)的值就可以了。方式是从s开始和从d开始进行2次单源多终点最短路径算法。然后枚举边即可。
该算法可以这样理解。因为替换最短路径里面的边，路径的长度只会变大或者不变。如果存在让更短路径变小的边，这本身就与最短路径是矛盾的。所以替换2条或者更多的边只会让路径变得更大。因此，只需考虑替换一条边的情况即可。

代码如下：

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int MAX_N = 5000 + 10;
struct Edge
{
    int nE;
    int nDis;
    Edge(int e, int d):nE(e), nDis(d) {}
};
vector<Edge> graph[MAX_N];
bool bVisit[MAX_N];
int nSDis[MAX_N];
int nEDis[MAX_N];

struct Node
{
    int nN;
    int nDis;

    bool operator < (const Node node) const
    {
        return nDis > node.nDis;
    }
};

int ShortestPath(int nS, int nE, int* nDis, int nN)
{
    priority_queue<Node> pq;
    memset(bVisit, false, sizeof(bVisit));
    for (int i = 1; i <= nN; i++)
    {
        nDis[i] = 0x7fffffff;
    }
    nDis[nS] = 0;
    Node head;
    head.nDis = 0, head.nN = nS;
    pq.push(head);

    while (pq.empty() == false)
    {
        Node head = pq.top();
        pq.pop();
        int nU = head.nN;
        if (bVisit[nU]) continue;
        bVisit[nU] = true;

        for (int i = 0; i < graph[nU].size(); ++i)
        {
            int nV = graph[nU][i].nE;
            int nLen = head.nDis + graph[nU][i].nDis;
            if (nLen < nDis[nV])
            {
                nDis[nV] = nLen;
                Node node;
                node.nDis = nLen;
                node.nN = nV;
                pq.push(node);
            }
        }
    }

    return nDis[nE];
}

int Second(int nS, int nE, int nN)
{
    int nShortest = ShortestPath(nS, nE, nSDis, nN);
    ShortestPath(nE, nS, nEDis, nN);

    int nAns = 0x7fffffff;

    for (int i = 1; i <= nN; ++i)
    {
        for (int j = 0; j < graph[i].size(); ++j)
        {
            int nU = i;
            int nV = graph[i][j].nE;
            int nLen = nSDis[i] + graph[i][j].nDis + nEDis[nV];
            if (nLen != nShortest)
            {
                nAns = min(nAns, nLen);
            }
        }
    }

    return nAns;
}

int main()
{
    int nN, nR;
    int nA, nB, nD;

    while (scanf("%d%d", &nN, &nR) == 2)
    {
        for (int i = 1; i <= nN; ++i)
        {
            graph[i].clear();
        }

        while (nR--)
        {
            scanf("%d%d%d", &nA, &nB, &nD);
            graph[nA].push_back(Edge(nB, nD));
            graph[nB].push_back(Edge(nA, nD));
        }
        printf("%d\n", Second(1, nN, nN));
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

这道题的意思是给定一个长N的整数序列，用一个大小为K的窗口从头开始覆盖，问第1-第N-K次窗口里面最大的数字和最小的数字。刚开始还以为优先级队列可以做，发现无法删除最前面的元素。估计用线段树这个题也是可以解得。用这个题学了下单调队列。
单调队列正如其名，是一个从小到大排序的队列，而且能够保证所有的元素入队列一次出队列一次，所以平摊到每个元素的复杂度就是O(1)。
对于这个题单调队列的使用。以序列1 3 -1 -3 5 3 6 7举例。
1）元素类型：一个结构体，包含数字大小和位置，比如(1，1），（3，2）。
2）插入操作：从队尾开始查找，把队尾小于待插入元素的元素全部删除，再加入待插入的元素。这个操作最坏的情况下是O(n)，但是我们采用聚集分析的方法，知道每个元素最多删除一次，那么N个元素删除N次，平摊到每一次操作的复杂度就是O(1)了。
3）删除队首元素：比如本文给的那个题，窗口一直往后移动，每一次移动都会删除一个元素，所以很可能队首会是要删除的元素，那么每次移动窗口的元素要进行一次检查，如果队首元素失效的话，就删掉队首元素。
代码的实现，我是包装deque实现了一个模版类。速度很不好，居然跑了11s多才过，幸亏给了12s的时间，看status又500多ms就过了的。估计数组实现会快很多。

代码如下：

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
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <deque>
#include <algorithm>
using namespace std;
#define MAX_N (1000000 + 100)
int nNum[MAX_N];
int nN, nK;

struct Small
{
    int nValue;
    int nIndex;
    Small(int nV, int index):nValue(nV), nIndex(index) {}
    bool operator < (const Small a) const
    {
        return nValue < a.nValue;
    }
};

struct Big
{
    int nValue;
    int nIndex;
    Big(int nV, int index):nValue(nV), nIndex(index) {}
    bool operator < (const Big a) const
    {
        return nValue > a.nValue;
    }
};

//单调队列
template <typename T> class Monoque
{
    deque<T> dn;

public:
    void Insert(T node)
    {
        int nPos = dn.size() - 1;
        while (nPos >=0  node < dn[nPos])
        {
            --nPos;
            dn.pop_back();
        }
        dn.push_back(node);
    }

    int Top()
    {
        return dn.front().nValue;
    }

    void Del(int nBeg, int nEnd)
    {
        if (dn.size() > 0)
        {
            if (dn.front().nIndex < nBeg || dn.front().nIndex > nEnd)
            {
                dn.pop_front();
            }
        }
    }
};

int main()
{
    while (scanf("%d%d", &nN, &nK) == 2)
    {
        int i;
        for (i = 0; i < nN; ++i)
        {
            scanf("%d", &nNum[i]);
        }
        Monoque<Small> minQ;
        Monoque<Big> maxQ;

        for (i = 0; i < nK; ++i)
        {
            minQ.Insert(Small(nNum[i], i));
        }

        for (i = 0; i < nN - nK; ++i)
        {
            printf("%d ", minQ.Top());
            minQ.Insert(Small(nNum[i + nK], i + nK));
            minQ.Del(i + 1, i + nK);
        }
        printf("%d\n", minQ.Top());

        for (i = 0; i < nK; ++i)
        {
            maxQ.Insert(Big(nNum[i], i));
        }

        for (i = 0; i < nN - nK; ++i)
        {
            printf("%d ", maxQ.Top());
            maxQ.Insert(Big(nNum[i + nK], i + nK));
            maxQ.Del(i + 1, i + nK);
        }
        printf("%d\n", maxQ.Top());
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

这是一个动态规划题，据说是背包问题的变形。我动态规划做得很少，解法一直按照算法导论的思想分解重叠子问题。
题意是用钱尽可能多的买物品，每种物品买一个，问有多少种买法。
我也想不出这是什么背包问题的变形，没做过几个背包问题，也没看过背包九讲。还是坚持认为正确的用状态描述成子问题就一定能解题的。今天和队友在做专题时候做到这个题，我一直做了一上午都没出来。
后面发现了个性质就可以直接转换为类似最简单的背包问题了。排序物品价值，从最大物品开始分解子问题，用剩余物品数和钱描述问题的状态。当前物品是否必须取，是根据当前的钱把剩下的物品全买了之后剩下的钱还是否大于当前物品的价值，如果大于就必须买，否则可以买或者不买。
为了正确描述问题的状态，必须事先排序价值数组，因为排序之后可以保证不能买当前物品的时候一定不能买前面的物品，那么我们对前面物品的处理就是正确的了。至此可以进行最简单的子问题分解了。到最后物品处理完之后（物品数为0），如果钱一点都没减少，那么(0, M) = 0，否则(0, M) = 1。注意这个边界处理，否则会wa。所以，需要先对价值数组排序，并计算出表示前N个物品价值和的数组。
做不出来的时候，翻了下别人的解法，一头雾水。看来还是算法导论的思想指导意义大多了。。。

代码如下：

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;
INT nAns[40][1010];
INT nValue[100];
INT nSum[100];
INT nN, nM;

INT GetAns(INT nNum, INT nMoney)
{
    if (nAns[nNum][nMoney] == -1)
    {
        if (nNum == 0)
        {
            nAns[nNum][nMoney] = 1;
            if (nMoney == nM)
            {
                nAns[nNum][nMoney] = 0;
            }
        }
        else
        {
            INT nRet = 0;

            if (nMoney - nSum[nNum - 1] >= nValue[nNum])
            {
                nRet = GetAns(nNum - 1, nMoney - nValue[nNum]);
            }
            else
            {
                if (nMoney >= nValue[nNum])
                {
                    nRet += GetAns(nNum - 1, nMoney - nValue[nNum]);
                }
                nRet += GetAns(nNum - 1, nMoney);
            }

            nAns[nNum][nMoney] = nRet;
        }
    }
    return nAns[nNum][nMoney];
}

int main()
{
    INT nT;

    scanf("%I64d", &nT);
    for (INT i = 1; i <= nT; ++i)
    {
        scanf("%I64d%I64d", &nN, &nM);
        for (INT j = 1; j <= nN; ++j)
        {
            scanf("%I64d", nValue[j]);
        }
        memset(nAns, -1, sizeof(nAns));
        sort(nValue + 1, nValue + nN + 1);
        nSum[0] = 0;
        for (INT j = 1; j <= nN; ++j)
        {
            nSum[j] = nSum[j - 1] + nValue[j];
        }
        printf("%I64d %I64d\n", i, GetAns(nN, nM));
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3k 阅读时长 ≈ 3 分钟

题意比较纠结，搜索了把题意。
给你一个素数P(P<=30000)和一串长为n的字符串str[]。字母 ‘*’ 代表0，字母a-z分别代表1-26，这n个字符所代表的数字分别代表f(1)、f(2)….f(n)。定义: f (k) = ∑0<=i<=n-1aiki (mod p) (1<=k<=n,0<=ai<P)，求a0、a1…..an-1。题目保证肯定有唯一解。
解题思路：高斯消元。根据上面的公式显然可以列出有n个未知数的n个方程式：

a0*1^0 + a1*1^1+a2*1^2+........+an-1*1^(n-1) = f(1)

a0*2^0 + a1*2^1+a2*2^2+........+an-1*2^(n-1) = f(2)

..............

a0*n^0 + a1*n^1+a2*n^2+........+an-1*n^(n-1) = f(n)

然后采用高斯消元法来解上面的方程组即可。
典型的高斯消元题，只是多了个modP，因此计算过程中可能需要扩展欧几里德算法。

说下所谓的高斯消元的思路，其实可以参看维基百科，

http://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF%E6%B6%88%E5%8E%BB%E6%B3%95，
大致过程是一直消变量。比如刚开始，消第一个变量，消完之后只让第一个方程含有第一个变量，然后消第二个变量，消完之后只让第二个方程含第二个变量，以此下去让最后的方程含最后一个变量，而且最后一个方程中对于前N-1个变量的系数都是0，这样就能解出这N个变量了。
关于自由元指的是这个变量可以取任何值，得出这样的结论是在消变量的过程中发现该变量的在第row个方程到第N方程中的系数都是0了，所以可以取任何值。判断无解的方式是，第row+1到第N个方程在高斯消元之后所有的系数必定是0，所以方程的值也必须是0。
求方程的解得过程是从N个解开始逆推，第N-1个方程也就包含2个变量了，第N个变量和第N-1个变量，以此下去，就可以解出方程组了。
具体的可以参照维基百科和代码仔细分析。还有演算法笔记上也有高斯消元的解释。

代码如下：

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX (70 + 10)

int nMatrix[MAX][MAX];
int nAns[MAX];
void InitMatrix(char* szStr, int nN, int nP)
{
    memset(nMatrix, 0, sizeof(nMatrix));
    for (int i = 0; i < nN; ++i)
    {
        nMatrix[i][nN] = (szStr[i] == '*' ? 0 : szStr[i] - 'a' + 1);
    }
    for (int i = 0; i < nN; ++i)
    {
        int nTemp = 1;
        for (int j = 0; j < nN; ++j)
        {
            nMatrix[i][j] = nTemp;
            nTemp = (nTemp * (i + 1)) % nP;
        }
    }
}

int egcd(int nA, int nB, int nX, int nY)
{
    if (nA < nB)swap(nA, nB);
    if (nB == 0)
    {
        nX = 1, nY = 0;
        return nA;
    }
    int nRet = egcd(nB, nA % nB, nX, nY);
    int nT = nX;
    nX = nY;
    nY = nT - (nA / nB) * nY;
    return nRet;
}

int Gauss(int nN, int nP)
{
    int nR, nC;
    for (nR = nC = 0; nR < nN  nC < nN; ++nR, ++nC)
    {
        if (nMatrix[nR][nC] == 0)
        {
            for (int i = nR + 1; i < nN; ++i)
            {
                if (nMatrix[i][nC])
                {
                    for (int j = nC; j <= nN; ++j)
                    {
                        swap(nMatrix[nR][j], nMatrix[i][j]);
                    }
                    break;
                }
            }
        }

        if (nMatrix[nR][nC] == 0)
        {
            nR--;    //自由元
            continue;
        }
        int nA = nMatrix[nR][nC];
        for (int i = nR + 1; i < nN; ++i)
        {
            if (nMatrix[i][nC])
            {
                int nB = nMatrix[i][nC];
                for (int j = nC; j <= nN; ++j)
                {
                    nMatrix[i][j] = (nMatrix[i][j] * nA - nMatrix[nR][j] * nB) % nP;
                }
            }
        }
    }
    for (int i = nR; i < nN; ++i)
    {
        if (nMatrix[i][nN])
        {
            return -1;//无解
        }
    }

    int nX, nY;
    for (int i = nN - 1; i >= 0; i--)
    {
        int nSum = 0;
        for (int j = i + 1; j < nN; ++j)
        {
            nSum = (nSum + nMatrix[i][j] * nAns[j]) % nP;
        }

        nSum = (nMatrix[i][nN] - nSum + nP * nP) % nP;

        egcd(nP, (nMatrix[i][i] + nP) % nP, nX, nY);
        nY = (nY + nP) % nP;
        nAns[i] = (nY * nSum + nP) % nP;//第i个解
    }
    return 1 << (nN - nR);//返回解的个数,本题有唯一解
}

int main()
{
    int nT;

    scanf("%d", &nT);
    while (nT--)
    {
        int nP;
        int nN;
        char szStr[MAX];
        scanf("%d%s", nP, szStr);
        nN = strlen(szStr);
        InitMatrix(szStr, nN, nP);
        Gauss(nN, nP);
        for (int i = 0; i < nN; ++i)
        {
            printf("%d%s", nAns[i], i == nN - 1 ? "\n" : " ");
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.4k 阅读时长 ≈ 3 分钟

这个是求扩展离散对数问题。XY mod Z = K，给出X，Z，K，求Y。 当Z是素数的时候直接用baby-step算法即可了。但是，模数不是素数的情况怎么办了。
方程a^X = b % c，可以进行一系列的转化。假设d = gcd(a,c)，由a^(x-1) a = b % c，知道a^(x-1)要存在必须满足gcd(a,c) | b，如果满足这个条件，那么我们可以在方程2边同时除以d，方程是不变的。因为a^x = b + k c，再除以公约数d，得到方程a^(x-1) a / d = b / d + k c / d。根据以上推论，我们可以不断的除以d，直到gcd(a,c)=1。
假设我们除了k次，那么方程转化为a^(x-k) a^k/d^k = b / d^k + k c / d^k。令d = a^k/d^k，b’ = b / d^k，c’ = c / d^k，x’ = x - k，方程转化为a^x’ d = b’ % c’，得到a^x’ = b’ d^-1 % c’。
现在直接用baby-step解方程a^x’ = b’ * (d^-1) % c’即可。注意到x=x’+k，如果存在x小于k的解，那么x’小于0，但是由baby-step是不会求负的次数的，所以需要先枚举一下是否存在小于k的解，由于输入的数据不会超过10^9的，假设k不超过50进行枚举即可了。

代码如下：

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long INT;
#define MAX (1000000)
INT nData[MAX];
INT nKey[MAX];

INT HashPos(INT key)
{
    return ((unsigned)(key ^ 0xA5A5A5A5)) % MAX;
}

void HashAdd(INT key, INT data)
{
    INT nPos = HashPos(key);
    while (nData[nPos] != -1)
    {
        nPos = (nPos + 1) % MAX;
    }
    nData[nPos] = data;
    nKey[nPos] = key;
}

INT HashQuery(INT key)
{
    INT nPos = HashPos(key);
    while (nData[nPos] != -1)
    {
        if (nKey[nPos] == key)
        {
            return nData[nPos];
        }
        nPos = (nPos + 1) % MAX;
    }

    return -1;
}

INT MultMod(INT nA, INT nB, INT nC)
{
    INT nAns = 0;
    while (nB)
    {
        if (nB  1)
        {
            nAns = (nAns + nA) % nC;
        }
        nA = (2 * nA) % nC;
        nB >>= 1;
    }
    return nAns;
}

INT PowerMod(INT nA, INT nX, INT nC)
{
    INT nAns = 1;
    nA %= nC;
    while (nX)
    {
        if (nX  1)
        {
            nAns = MultMod(nAns, nA, nC); 
        }
        nA = MultMod(nA, nA, nC);
        nX >>= 1;
    }
    return nAns;
}

INT gcd(INT nA, INT nB)
{
    if (nA < nB)swap(nA, nB);
    while (nB)
    {
        INT nT = nA;
        nA = nB;
        nB = nT % nB;
    }
    return nA;
}
//d = nA * nX + nB * nY(nA > nB, nA是模数)
INT egcd(INT nA, INT nB, INT nX, INT nY)
{
    if (nA < nB)swap(nA, nB);
    if (nB == 0)
    {
        nX = 1;
        nY = 0;
        return nA;
    }
    INT nRet = egcd(nB, nA % nB, nX, nY);
    INT nT = nX;
    nX = nY;
    nY = nT - (nA / nB) * nY;
    return nRet;
}

INT GetAns(INT nA, INT nB, INT nC)
{
    if (nC == 0)return -1;
    //先枚举0-50,扩展baby-step的过程可能会漏掉这些解
    INT nTemp = 1;
    nB %= nC;
    for (INT i = 0; i <= 50; ++i)
    {
        if (nTemp == nB)
        {
            return i;
        }
        nTemp = MultMod(nTemp, nA, nC);
    }

    //如果nC不是素数,那么方程nA^x = nB + k*nC
    //可以不到除以gcd(nC,nA)
    //如果gcd(nC,nA)|nB不成立,方程无解，
    //这个由a*x=b%c有解必须满足gcd(a,c)|b一样
    INT d;
    INT nD = 1;//nD最后是A^k次,k是nC中因子d的次数
    INT k = 0;
    while ((d = gcd(nC, nA)) != 1)
    {
        k++;
        nC /= d;
        if (nB % d)return -1;
        nB /= d;
        nD = MultMod(nD, nA / d, nC);
    }
    //现在方程转化为nA^(x-k) * nA^k/d^k = nB/d^k % nC/d^k
    //其实就是方程2侧除以d^k次而已,这样的做法与原方程是等价的
    //令nD = nA^k/d^k,则nA^x'*nD = nB' % nC',
    //解该方程,那么x=x'+k
    //注意,如果x<k,那么x'为负数,baby-step无法求出,故在函数开头进行枚举
    memset(nKey, -1, sizeof(nKey));
    memset(nData, -1, sizeof(nData));
    INT nM = ceil(sqrt(1.0 * nC));
    nTemp = 1;
    for (INT j = 0; j <= nM; ++j)
    {
        HashAdd(nTemp, j);
        nTemp = MultMod(nTemp, nA, nC);
    }
    INT nK = PowerMod(nA, nM, nC);
    for (int i = 0; i <= nM; ++i)
    {
        INT x, y;
        egcd(nC, nD, x, y);//y = nD^-1,nD = nD*(nA^m)^i
        y = (y + nC) % nC;//这句话是必须的,y很可能就是负数
        INT nR = MultMod(y, nB, nC);//nR=nB*nD^-1
        int j = HashQuery(nR);
        if (j != -1)
        {
            return nM * i + j + k;
        }

        nD = MultMod(nD, nK, nC);
    }
    return -1;
}

int main()
{
    INT nA, nB, nC;

    while (scanf("%I64d%I64d%I64d", &nA, &nC, &nB), nA + nB + nC)
    {
        INT nAns = GetAns(nA, nB, nC);
        if (nAns == -1)
        {
            printf("No Solution\n");
        }
        else
        {
            printf("%I64d\n", nAns);
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

这个题很奇葩了。题意是给出个数字L，假如存在一个数K使得L K = 888…，求888…的最小长度，如果不存在这样的K，那么输出0。我是什么思路也没有了，拖了几天了，数论搞死我了，只能找答案了。
我看到个比较靠谱的推法。首先，888… = 111… 8=(10^0+10^1+…+10^m-1) 8=(10^m - 1) / 9 8，PS：m代表888…的长度。
好吧，终于化成指数了，现在有8 (10^m-1)/9=K L，最小的m就是我们要求的答案啦。

方式1：
=> 8 (10^m-1) = 9 k L
=> 8 / d (10^m-1) = 9 k L / d，d=gcd(8,9L)
=> 10^m-1 = 0 % 9 L / gcd(8, 9L) = 0 % 9 L/gcd(8,L)，(由于gcd(8/d,9L/d)=1，那么10^m-1必然是9 L / d的倍数了)。
=> 10^m = 1 % 9 L / gcd(8,L)
方式2：
=> 8 (10^m-1)/9 = 0 % L
=> 8 (10^m-1) = 0 % 9 L(这步的推出，比如x/9 = k n，那么x = 9 k n了，显然成立)
=> 10^m-1 = 0 % 9 L / gcd(9 L,8)，假如，d = gcd(9 L,8)，那么有8 / d (10^m - 1) = k 9 L/d，因为8/d不可能是9 L / d的倍数，所以10^m-1必定是9 L / d的倍数，所以10^m-1 = 0 % 9 L / gcd(9 L,8))，=>，10^m - 1 = 0 % 9 L / gcd(L, 8),
(因为gcd(9,8)=1)。
=> 10^m = 1 % 9 L/gcd(8, L)

至此，2种方式都推出了，10^m = 1 % 9 L / gcd(8,L) 。
那么怎么解答这个问题了，这个就用到了欧拉定理了。令p = 9 L / gcd(8,L)，那么有10^m = 1 % p。由欧拉定理知,Z p中所有的数字a均满足a^euler(p) = 1 % p。那么，10只要是p的乘法群中就肯定有解了。如果，10不在Z p中了，肯定是无解的。证明如下：
由a^x = 1%p，可以得到a^(x-1) a=1%p，要a^(x-1)存在，那么gcd(a,p)|1，那么gcd(a,p)必须是1。综上所述，要满足式子a^m=1%p，必须gcd(p,a)=1，即a必须是p的乘法群中的数字。现在的问题是求最小的m，由欧拉定理知道a^euler(p)=1%p，m再大就开始循环了。但是m可能会更小。比如，我们现在知道最小的m是min，那么有a^min=1%p，因为要满足a^euler(p)=1%p，那么a^euler(p)肯定能变换成(a^min)^k,至于k是多少就不知道了，当然也可以求出来。那么min就是euler(p)的一个因子，而且是最小的一个满足a^min=1%p的因子了。
现在就可以通过枚举euler(p)的因子，找到最小的因子min满足式子a^min = 1 % p就能解决本问题了。注意求a^m%p肯定是通过算法导论上面那种方法的,O(32)或者O(64)的复杂度，还有a b%m也需要自己模拟，因为可能a * b就溢出了。
代码如下，貌似代码还可以通过其它的改进加快速度。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long INT;

//10^m = 1 % (9*L / gcd(8, L)),求最小m
//p = 9 * L / gcd(8,L)
//gcd(p,10) != 1则p有2或者5的因子,2^m=1%p或者
//5^m=1%p无解,原式无解
//if(p)素数,m=euler(p) = p - 1
//否则,m一定是euler(p)的最小满足等式的因子
//因为(10^m)^n = 10^euler(p) = 1%p
INT gcd(INT a, INT b)
{
    if (a < b)swap(a, b);
    while (b)
    {
        INT t = a;
        a = b;
        b = t % b;
    }
    return a;
}

INT Euler(INT nN)
{
    INT nAns = 1;
    INT nMax = sqrt((double)nN) + 1;
    for (INT i = 2; i <= nMax; ++i)
    {
        if (nN % i == 0)
        {
            nAns *= i - 1;
            nN /= i;
            while (nN % i == 0)
            {
                nAns *= i;
                nN /= i;
            }
        }
    }
    if (nN != 1)nAns *= nN - 1;
    return nAns;
}

INT MultMod(INT a, INT b, INT mod)
{
    INT ans = 0;
    while (b)
    {
        if (b  1)
        {
            ans = (ans + a) % mod;
        }
        a = (2 * a) % mod;
        b >>= 1;
    }
    return ans;
}

INT ExpMod(INT base, INT exp, INT mod)
{
    INT ans = 1;
    base %= mod;
    while (exp)
    {
        if (exp  1)
        {
            ans = MultMod(ans, base, mod);
        }
        base = MultMod(base, base, mod);
        exp >>= 1;
    }
    return ans % mod;
}

INT GetAns(INT p)
{
    INT u = Euler(p);
    INT nMax = sqrt((double)u) + 1;
    INT nAns = u;
    for (INT i = 1; i <= nMax; ++i)
    {
        if (u % i == 0)
        {
            if (ExpMod(10, i, p) == 1)
            {
                nAns = i;
                break;
            }
            if (ExpMod(10, u / i, p) == 1)
            {
                nAns = min(nAns, u / i);
            }
        }
    }
    return nAns;
}

int main()
{
    INT nL;
    INT nCase = 1;

    while (scanf("%I64d", &nL), nL)
    {
        INT p = 9 * nL / gcd(nL, 8);
        if (gcd(p, 10) != 1)
        {
            printf("Case %I64d: 0\n", nCase++);
            continue;
        }
        printf("Case %I64d: %I64d\n", nCase++, GetAns(p));
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

此题的意思是分解大数字，数字的范围是Longlong级别的，好像不能暴力的样子。但是，题目给出了个条件，最多只有一个因子的大小超过1000000。哈哈，这就是暴点啊。既然，如此直接枚举1000000以内的因子就行了，剩余的部分如果大于10的6次肯定是N的因子了，就不用暴力了。如果小于10的6次肯定是1啦，因为2-1000000的因子都被处理了啊。
这样这个题就不会超时了。确实，暴力是需要技巧的。还要注意uva上要用%lld输入。

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
#include <stdio.h>
#include <math.h>
typedef long long LL;
#define MAX (6000000)
bool bPrime[MAX];
int nPrime[MAX];
int nNum;

void InitPrime()
{
    LL nMax = sqrt(MAX) + 1;
    bPrime[0] = bPrime[1] = true;
    for (int i = 2; i <= nMax; ++i)
    {
        if (!bPrime[i])
        {
            for (int j = 2 * i; j < MAX; j += i)
            {
                bPrime[j] = true;
            }
        }
    }
    for (int i = 2; i < MAX; ++i)
    {
        if (!bPrime[i])
            nPrime[nNum++] = i;
    }

}

bool IsPrime(LL nN)
{
    if (nN < MAX) return !bPrime[nN];
    LL nMax = sqrt((double)nN) + 1;
    for (LL j = 0, i = nPrime[j]; i <= nMax; ++j, i = nPrime[j])
    {
        if (nN % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    LL nN;

    InitPrime();
    while (scanf("%lld", &nN), nN >= 0)
    {
        if (nN <= 2)
        {
            printf("%-lld\n\n", nN);
            continue;
        }

        int nMax = sqrt((double)nN)+ 1;
        for (LL i = 2; i <= 1000000  i <= nMax; ++i)
        {
            while (nN % i == 0)
            {
                printf("    %-lld\n", i);
                nN /= i;
            }
            if (nN < 6000000  IsPrime(nN))
            {
                break;
            }
        }
        if (nN != 1)
            printf("    %-lld\n", nN);
        printf("\n");
    }

    return 0;
}