STEP BY STEP

发表于 分类于 ， 阅读次数： 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;
}

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

题意就是给出个数n，求Σgcd(i,n)(1<=i<=n)。感觉好奇葩的题目，数论的题确实比较难想，没看出跟欧拉函数有什么关系。很纠结，没心情没时间继续想了。看了discussion，然后又去搜了下答案，发现有个哥们也得非常不错，就看了下思路了。
这个题的解法是枚举i(1<=i<=n)，如果i|n，那么答案加上euler(n/i) i。其实ans = Σi euler(n/i)(i<=i<=n而且i|n)。意思是从1到n的所有数字i，如果i是n的因子，那么计算 i euler(n/i)，加入答案中，euler是欧拉函数的意思。
为什么是这样的了。比如，1到n中有m个数字和n拥有公共的最大因子i，那么就需要把m i加入答案中。问题是如何计算m的个数。因为gcd(m,n) = i，可以得到gcd(m/i,n/i)=1，那么m/i就是n/i的乘法群中的数字了，那么一共存在euler(n/i)个m/i了，那么就可以推出m的个数就是euler(n/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
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
#include <stdio.h>
#include <math.h>
#define MAX (6000000)
bool bPrime[MAX];

void InitPrime()
{
    int nMax = sqrt((double)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;
            }
        }
    }
}

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

long long Euler(long long nN)
{
    long long nAns = 1;

    //printf("nN:%I64d,", nN);
    if (IsPrime(nN))nAns = nN - 1;
    else
        for (int i = 2; i <= nN; ++i)
        {
            if (nN % i == 0)
            {
                nAns *= i - 1;
                nN /= i;
                while (nN % i == 0)
                {
                    nAns *= i;
                    nN /= i;
                }
                if (IsPrime(nN))
                {
                    nAns *= nN - 1;
                    break;
                }
            }
        }

    //printf("nAns:%I64d\n", nAns);
    return nAns;
}

int main()
{
    long long nN;

    InitPrime();
    while (scanf("%I64d", &nN) == 1)
    {
        long long nAns = 0;
        long long nMax = sqrt((double)nN) + 1e-8;
        for (long long i = 1; i <= nMax; ++i)
        {
            if (nN % i == 0)
            {
                //printf("i:%I64d\n", i);
                nAns += i * Euler(nN / i);
                if (i * i != nN)
                    nAns += (nN / i) * Euler(i);
            }
        }
        printf("%I64d\n", nAns);
    }

    return 0;
}

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

这个题是求原根的个数。所谓原根，意思是给定一个数n，存在数g，g^j能够产生乘法群Zn中所有的数字。即g^j = {x|x与n互质,1<=x<n}。如果n是奇素数p(大于2的素数)，那么满足g^j={1,2,…,p-1}。
这个题目要求求原根的个数。由费马定理由,对任意1<=x<p，即Zp中的数字，都由x^(p-1) = 1 % p。从费马定理可以看出，再往下计算就开始循环了。那么有,x^i%p(1<=i<p) = {1, 2, 3,…,p-1},意思是能够生成Zp中的所有数字。
根据上面的那个式子可以得到，x^i%(p-1)(1<=i<p) = {0, 1, 2,…,p-2}。 如果由gcd(x,p-1) = 1,那么必然存在某个x^i，使得x^ix = (p-1)%p。
因此可以得到，原根的个数是p-1的乘法群中元素的个数，也就是欧拉函数(p-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
#include <stdio.h>
#include <math.h>
#define MAX (5000000)
bool bPrime[MAX];
void InitPrime()
{
    int nMax = sqrt((double)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;
            }
        }
    }
}
bool IsPrime(int nN)
{
    if (nN < MAX)return !bPrime[nN];
    int nMax = sqrt((double)nN) + 1;
    for (int i = 2; i <= nMax; ++i)
    {
        if (nN % i == 0)
            return false;
    }
    return true;
}
int main()
{
    int nN;
    InitPrime();
    while (scanf("%d", &nN) == 1)
    {
        nN--;
        int nAns = 1;
        if (IsPrime(nN))
        {
            nAns = nN - 1;
        }
        else
        {
            for (int i = 2; i <= nN; ++i)
            {
                if (nN % i == 0)
                {
                    nAns *= i - 1;
                    nN /= i;
                    while (nN % i == 0)
                    {
                        nAns *= i;
                        nN /= i;
                    }
                    if (IsPrime(nN))
                    {
                        nAns *= nN - 1;
                        break;
                    }
                }
            }
        }
        printf("%d\n", nAns);
    }
    return 0;
}

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

这是个求离散对数的问题。以前学密码学基础的时候也接触过，但是没想到acm里面还会有这样的习题。问题的意思是给定素数P，给出方程a^x = b % p，注意有模的方程等式2边都是取模数的意思。解这样的方程有一个固定的算法，叫做baby-step算法。但是，注意限定条件是p必须是素数。
下面的图描述了这个算法：


意思很清楚，就是假设x = i m + j，那么方程可以转化为b(a^-m)^i = a^j % p。先计算出右边的值，存储在一张表里面，然后从小到大枚举左边的i（0<=i<m)，率先满足等式的就是最小的解x。
poj上面这个题用map存储(a^j,j)对的时候会超时，改成hash表存储才能过，额，毕竟理论复杂度不是一个数量级的。我的hash表是开了2个数组，一个键，一个值，用来相互验证，槽冲突的话，一直往后找位置。感觉这样的做法没有链式hash复杂度平均的样子。
代码如下：

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

#define MAX (1000000)
long long nData[MAX];
long long nKey[MAX];
long long egcd(long long a, long long b, long long x, long long y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long ret = egcd(b, a % b, x, y);
    long long t = x;
    x = y;
    y = t - (a / b) * y;
    return ret;
}

long long GetPos(long long key)
{
    return (key ^ 0xA5A5A5A5) % MAX;
}

void Add(long long key, long long data)
{
    long long nPos = GetPos(key);
    while (nData[nPos] != -1)
    {
        nPos = (nPos + 1) % MAX;
    }
    nData[nPos] = data;
    nKey[nPos] = key;
}

int Query(int key)
{
    int nPos = GetPos(key);

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

long long BabyStep(long long nA, long long nB, long long nP)
{
    long long nM = ceil(sqrt((double)(nP - 1)));
    long long x, y;
    egcd(nP, nA, x, y);//y是nA%p的乘法逆
    y = (y + nP) % nP;
    long long nTemp = 1;
    long long c = 1;//c是nA的—m次
    memset(nData, -1, sizeof(nData));
    memset(nKey, -1, sizeof(nKey));
    for (long long j = 0; j < nM; ++j)
    {
        Add(nTemp, j);
        nTemp = (nTemp * nA) % nP;
        c = (c * y) % nP;
    }

    long long r = nB;
    for (int i = 0; i < nM; ++i)
    {
        long long j = Query(r);
        if (j != -1)
        {
            return i * nM + j;
        }
        r = (r * c) % nP;
    }
    return -1;
}

int main()
{
    long long nP, nB, nN;

    while (scanf("%I64d%I64d%I64d", &nP, &nB, &nN) == 3)
    {
        long long nAns = BabyStep(nB, nN, nP);
        if (nAns == -1)printf("no solution\n");
        else printf("%I64d\n", nAns);
    }

    return 0;
}

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

这是今天想通的一个数论题，还是挺有意思的，想出来的那一瞬间yeah了一下，可是我悲剧的粗心习惯，还是交了3次才过，nm数中间空格都错了，又忘记打空行，明明字符串从25列开始，中间是4个空格的，我nc的打了5个空格，就pe了，还有不仔细看输出要求，没有输出空行，最近真没状态啊。
其实，这个题想通了就很简单了，还是数论里面的群的概念，就是加法群的生成群啊，打着随机数的幌子而已。由于又没有限定种子，限定对答案也没有影响，假设种子是0，那么数列可以表示为a step，数列要能够生成0 - mod-1中所有的数字，那么就有a step = b % mod(0<=b<mod)。
哈哈，上面那个式子就是a x = b % n这个线性同余方程了，只是有很多b了。要方程有解，不是需要满足条件gcd(a,n) | b么，意思b是gcd(a,n)的整数倍了。但是0 <= b < n啊，b会是1了，那么gcd(a,n)一定是1了哦。那么直接判断gcd(step,mod)是否为1就行了，哈哈。
关于线性同余方程ax=b%n，要有解的条件gcd(a,n)|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
#include <stdio.h>
#include <algorithm>
using namespace std;

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 main()
{
    int nStep, nMod;

    while (scanf("%d%d", &nStep, &nMod) == 2)
    {
        printf("%10d%10d    %s\n\n", nStep, nMod,
               gcd(nStep, nMod) == 1 ? "Good Choice" : "Bad Choice");
    }

    return 0;
}