這個是求擴(kuò)展離散對數(shù)問題。
XY mod Z = K，給出X，Z，K，求Y。
當(dāng)Z是素數(shù)的時候直接用baby-step算法即可了。但是，模數(shù)不是素數(shù)的情況怎么辦了。
方程a^X = b % c，可以進(jìn)行一系列的轉(zhuǎn)化。假設(shè)d = gcd(a,c)，由a^(x-1)*a = b % c，知道a^(x-1)要存在必須滿足
gcd(a,c)|b，如果滿足這個條件，那么我們可以在方程2邊同時除以d，方程是不變的。因為a^x = b + k * c，再除以公約數(shù)
d，得到方程a^(x-1)*a/d = b / d + k * c / d。根據(jù)以上推論，我們可以不斷的除以d，直到gcd(a,c)=1。
假設(shè)我們除了k次，那么方程轉(zhuǎn)化為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，方程轉(zhuǎn)化為a^x' * d = b' % c'，得到a^x' = b' * d^-1 % c'。
現(xiàn)在直接用baby-step解方程a^x' = b' * (d^-1) % c'即可。注意到x=x'+k，如果存在x小于k的解，那么x'小于0，但是
由baby-step是不會求負(fù)的次數(shù)的，所以需要先枚舉一下是否存在小于k的解，由于輸入的數(shù)據(jù)不會超過10^9的，假設(shè)k不超過50
進(jìn)行枚舉即可了。
代碼如下：
#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是模數(shù))
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,擴(kuò)展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不是素數(shù),那么方程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的次數(shù)
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);
}
//現(xiàn)在方程轉(zhuǎn)化為nA^(x-k) * nA^k/d^k = nB/d^k % nC/d^k
//其實就是方程2側(cè)除以d^k次而已,這樣的做法與原方程是等價的
//令nD = nA^k/d^k,則nA^x'*nD = nB' % nC',
//解該方程,那么x=x'+k
//注意,如果x<k,那么x'為負(fù)數(shù),baby-step無法求出,故在函數(shù)開頭進(jìn)行枚舉
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很可能就是負(fù)數(shù)
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;
}
這個題很奇葩了。題意是給出個數(shù)字L，假如存在一個數(shù)K使得L*K = 888...，求888...的最小長度，如果不存在這樣的K，那么輸出0。
我是什么思路也沒有了，拖了幾天了，數(shù)論搞死我了，只能找答案了。
我看到個比較靠譜的推法。首先，888...=111...*8=(10^0+10^1+...+10^m-1)*8=(10^m - 1)/9*8，PS：m代表888...的長度。
好吧，終于化成指數(shù)了，現(xiàn)在有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的倍數(shù)了)。
=> 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
的倍數(shù)，所以
10^m-1必定是9*L/d的倍數(shù)，所以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中所有的
數(shù)字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的乘法群中的數(shù)字。
現(xiàn)在的問題是求最小的m，由歐拉定理知道a^euler(p)=1%p，m再大就開始循環(huán)了。但是m可能會更小。比如，我們現(xiàn)在知道最小的m
是min，那么有a^min=1%p，因為要滿足a^euler(p)=1%p，那么a^euler(p)肯定能變換成
(a^min)^k,至于k是多少就不知道了，當(dāng)然
也可以求出來。那么min就是euler(p)的一個因子，而且是最小的一個滿足a^min=1%p的因子了。
現(xiàn)在就可以通過枚舉euler(p)的因子，找到最小的因子min滿足式子a^min = 1 % p就能解決本問題了。
注意求a^m%p肯定是通過算法導(dǎo)論上面那種方法的,O(32)或者O(64)的復(fù)雜度，還有a*b%m也需要自己模擬，因為可能a*b就溢出了。
代碼如下，貌似代碼還可以通過其它的改進(jìn)加快速度。
#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)素數(shù),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;
}
此題的意思是分解大數(shù)字，數(shù)字的范圍是Longlong級別的，好像不能暴力的樣子。但是，題目給出了個條件，最多只有一個因
子的大小超過1000000。哈哈，這就是暴點啊。既然，如此直接枚舉1000000以內(nèi)的因子就行了，剩余的部分如果大于10的6次
肯定是N的因子了，就不用暴力了。如果小于10的6次肯定是1啦，因為2-1000000的因子都被處理了啊。
這樣這個題就不會超時了。確實，暴力是需要技巧的。還要注意uva上要用%lld輸入。
#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;
}
題意就是給出個數(shù)n，求
Σgcd(i,n)(1<=i<=n)。感覺好奇葩的題目，數(shù)論的題確實比較難想，沒看出跟歐拉函數(shù)有什么關(guān)系。
很糾結(jié)，沒心情沒時間繼續(xù)想了。看了discussion，然后又去搜了下答案，發(fā)現(xiàn)有個哥們也得非常不錯，就看了下思路了。
這個題的解法是枚舉i(1<=i<=n)，如果i|n，那么答案加上euler(n/i)*i。其實ans = Σi*euler(n/i)(i<=i<=n而且i|n)。
意思是從1到n的所有數(shù)字i，如果i是n的因子，那么計算i*euler(n/i)，加入答案中，euler是歐拉函數(shù)的意思。
為什么是這樣的了。比如，1到n中有m個數(shù)字和n擁有公共的最大因子i，那么就需要把m*i加入答案中。問題是如何計算m的個數(shù)。
因為gcd(m,n) = i，可以得到gcd(m/i,n/i)=1，那么m/i就是n/i的乘法群中的數(shù)字了，那么一共存在euler(n/i)個m/i了，那么就
可以推出m的個數(shù)就是euler(n/i)。
代碼如下:
#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;
}
這個題是求原根的個數(shù)。所謂原根，意思是給定一個數(shù)n，存在數(shù)g，g^j能夠產(chǎn)生乘法群Zn*中所有的數(shù)字。即g^j = {x|x與n互質(zhì),
1<=x<n}。如果n是奇素數(shù)p(大于2的素數(shù))，那么滿足g^j={1,2,...,p-1}。
這個題目要求求原根的個數(shù)。由費馬定理由,對任意1<=x<p，即Zp*中的數(shù)字，都由x^(p-1) = 1 % p。從費馬定理可以看出，
再往下計算就開始循環(huán)了。那么有,x^i%p(1<=i<p) = {1, 2, 3,...,p-1},意思是能夠生成Zp*中的所有數(shù)字。
根據(jù)上面的那個式子可以得到，x^i%(p-1)(1<=i<p) = {0, 1, 2,...,p-2}。 如果由gcd(x,p-1) = 1,那么必然存在某個x^i，
使得x^i*x = (p-1)%p。
因此可以得到，原根的個數(shù)是p-1的乘法群中元素的個數(shù)，也就是歐拉函數(shù)(p-1)。
代碼如下：
#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;
}
這是個求離散對數(shù)的問題。以前學(xué)密碼學(xué)基礎(chǔ)的時候也接觸過，但是沒想到acm里面還會有這樣的習(xí)題。
問題的意思是給定素數(shù)P，給出方程a^x = b % p，注意有模的方程等式2邊都是取模數(shù)的意思。解這樣的方程有一個固定的算法，
叫做baby-step算法。但是，注意限定條件是p必須是素數(shù)。
下面的圖描述了這個算法：
意思很清楚，就是假設(shè)x = i * m + j，那么方程可以轉(zhuǎn)化為b*(a^-m)^i = a^j % p。先計算出右邊的值，存儲在一張表里面，
然后從小到大枚舉左邊的i（0<=i<m)，率先滿足等式的就是最小的解x。
poj上面這個題用map存儲(a^j,j)對的時候會超時，改成hash表存儲才能過，額，畢竟理論復(fù)雜度不是一個數(shù)量級的。我的hash表是
開了2個數(shù)組，一個鍵，一個值，用來相互驗證，槽沖突的話，一直往后找位置。感覺這樣的做法沒有鏈?zhǔn)絟ash復(fù)雜度平均的樣子。
代碼如下：
#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;
}
這是今天想通的一個數(shù)論題，還是挺有意思的，想出來的那一瞬間yeah了一下，可是我悲劇的粗心習(xí)慣，還是交了3次才過，nm數(shù)中間空
格都錯了，又忘記打空行，明明字符串從25列開始，中間是4個空格的，我nc的打了5個空格，就pe了，還有不仔細(xì)看輸出要求，沒有輸出空
行，最近真沒狀態(tài)啊。
其實，這個題想通了就很簡單了，還是數(shù)論里面的群的概念，就是加法群的生成群啊，打著隨機(jī)數(shù)的幌子而已。由于又沒有限定種子，限定
對答案也沒有影響，假設(shè)種子是0，那么數(shù)列可以表示為a*step，數(shù)列要能夠生成0 - mod-1中所有的數(shù)字，那么就有a*step = b % mod
(0<=b<mod)。
哈哈，上面那個式子就是a*x=b%n這個線性同余方程了，只是有很多b了。要方程有解，不是需要滿足條件gcd(a,n)|b么，意思b是
gcd(a,n)的整數(shù)倍了。但是0<=b<n啊，b會是1了，那么gcd(a,n)一定是1了哦。那么直接判斷gcd(step,mod)是否為1就行了，哈哈。
關(guān)于線性同余方程a*x=b%n，要有解的條件gcd(a,n)|b的解釋，還是參看算法導(dǎo)論或者其它資料吧。。。
代碼就非常簡單了，如下：
#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;
}
這個題目就是解線性同余方程，(a + n*c) % 2的k次 = b % 2的k次。既然以前是學(xué)信安的，對數(shù)論本來就不排斥，最近還好好看了下算
法導(dǎo)論。這個方程轉(zhuǎn)換為n*c = (b-a) % 2的k次。根據(jù)數(shù)論的知識， ax = b%n，需要保證gcd(a,n)|b，意思b是gcd(a,n)的倍數(shù)，這個
一下子也很難解釋清楚啊，不滿足這個條件，就是沒解了。還有，如果有解的話，解的個數(shù)就是d = gcd(a,n)。而且其中一個解是x0 = x'(b
/ d)，其中x'是用擴(kuò)展歐幾里德算法求出來的，滿足關(guān)系式a*x'+n*y'=d。
但是這個題不僅僅用到數(shù)論的這些知識，因為必須求滿足條件的最小解，而如果有解的話是d個，而且滿足解x = x0 + i(b/d)，
（1<=i<=d)。既然要求最小的解，那么對解mod(n/d)即可了，因為它們之間的差都是n/d的倍數(shù)。
代碼如下：
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
//擴(kuò)展歐幾里德算法
//d = a * x + b * y，d是a和b的最大公約數(shù)
long long egcd(
long long a,
long long b,
long long& x,
long long& y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
else {
long long nRet = egcd(b, a % b, x, y);
long long t = x;
x = y;
y = t - (a / b) * y;
return nRet;
}
}
int main()
{
long long nA, nB, nC, nK;
while (scanf("%I64d%I64d%I64d%I64d", &nA, &nB, &nC, &nK),
nA || nB || nC || nK)
{
long long x, y;
long long n = pow((
double)2, (
double)nK) + 1e-8;
long long d = egcd(n, nC, x, y);
long long b = (nB - nA + n) % n;
if (b % d)
//如果d | b失敗
{
printf("FOREVER\n");
}
else {
//printf("y:%I64d, b:%I64d, d:%I64d n:%I64d\n", y, b, d, n);
y = (y + n) % n;
long long ans = (y * (b / d)) % (n / d);
printf("%I64d\n", ans);
}
}
return 0;
}
這個題目是求N！后面有多少個0，注意N可能最大到10的9次。哈哈，直接枚舉1-N有多少個2和5的因子，然后取小的值肯定會超時的。
但是，我還是試了下，果斷超時了。
那就只有想數(shù)學(xué)結(jié)論了，果斷想到1-N中能被2整除的數(shù)字有N / 2。哈哈，再往后思考下，發(fā)現(xiàn)1-N中能被4整除的數(shù)字有N / 4個，再往后
就是N / 8，一直到N 除以2的某個次方為0為止，那么把所有的值加起來就是2的因子的個數(shù)了。求5的因子的個數(shù)也是這樣的方法了。
很明顯，5的因子的個數(shù)一定會小于等于2的因子的個數(shù)。那么直接求5的因子的個數(shù)就行了。由于，N / 5的時候用到了向下取整，
所以不能用等比數(shù)列求和公式，怎么把答案弄成一個公式，還不知道了。
PS：其實我這種思路的靈感來自于篩選素數(shù)的方法了。
代碼如下：
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int GetAns(
int nN)
{
int nAns = 0;
while (nN)
{
nAns += nN / 5;
nN /= 5;
}
return nAns;
}
int main()
{
int nT;
scanf("%d", &nT);
while (nT--)
{
int nN;
scanf("%d", &nN);
printf("%d\n", GetAns(nN));
}
return 0;
}
這個題一看就知道是求歐拉函數(shù)。歐拉函數(shù)描述的正式題意。歐拉函數(shù)的理解可以按照算法導(dǎo)論上面的說法，對0-N-1進(jìn)行篩選素數(shù)。
那么公式n
∏(1-1/p)，其中p是n的素數(shù)因子，就可以得到直觀的理解了。但是計算的時候，會將這個式子變形下，得到另外一個形式。
如圖所示：
.jpg)
但是這個題，需要考慮下，有可能n是個大素數(shù)，直接進(jìn)行因子分解的話會超時的。怎么辦了，只能在分解的時候判斷n是不是已經(jīng)成為
素數(shù)了，如果是素數(shù)，答案再乘以n-1就行了。為了加快判斷，我用5mb的空間搞了個素數(shù)表，大于5000000的數(shù)字只能循環(huán)判斷了。
代碼如下，注意求歐拉函數(shù)的代碼部分：
#include <stdio.h>
#include <math.h>
#define MAX (5000000)
bool bPrime[MAX];//false表示素數(shù)
void InitPrime()
{
bPrime[0] = bPrime[1] = true;
int nMax = sqrt((double)MAX) + 1;
for (int i = 2; i <= nMax; ++i)
{
if (!bPrime[i])
for (int j = i * 2; j < MAX; j += i)
{
bPrime[j] = true;
}
}
}
bool IsPrime(int nN)
{
if (nN < MAX)
{
return !bPrime[nN];
}
else
{
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), nN)
{
if (nN == 1){printf("0\n");continue;}
int nAns = 1;
for (int i = 2; i <= nN; ++i)
{
if (IsPrime(nN))
{
nAns *= nN - 1;
break;
}
if (nN % i == 0)
{
nAns *= i - 1;
nN /= i;
while (nN % i == 0)
{
nAns *= i;
nN /= i;
}
}
}
printf("%d\n", nAns);
}
return 0;
}