这个是求扩展离散对数问题。
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
进行枚举即可了。
代码如下：
#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;
}
这个题很奇葩了。题意是给出个数字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就溢出了。
代码如下，貌似代码还可以通过其它的改进加快速度。
#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;
}
此题的意思是分解大数字，数字的范围是Longlong级别的，好像不能暴力的样子。但是，题目给出了个条件，最多只有一个因
子的大小超过1000000。哈哈，这就是暴点啊。既然，如此直接枚举1000000以内的因子就行了，剩余的部分如果大于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;
}
题意就是给出个数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)。
代码如下:
#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;
}
这个题是求原根的个数。所谓原根，意思是给定一个数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^i*x = (p-1)%p。
因此可以得到，原根的个数是p-1的乘法群中元素的个数，也就是欧拉函数(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;
}
这是个求离散对数的问题。以前学密码学基础的时候也接触过，但是没想到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复杂度平均的样子。
代码如下：
#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;
}
这是今天想通的一个数论题，还是挺有意思的，想出来的那一瞬间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就行了，哈哈。
关于线性同余方程a*x=b%n，要有解的条件gcd(a,n)|b的解释，还是参看算法导论或者其它资料吧。。。
代码就非常简单了，如下：
#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次。既然以前是学信安的，对数论本来就不排斥，最近还好好看了下算
法导论。这个方程转换为n*c = (b-a) % 2的k次。根据数论的知识， ax = b%n，需要保证gcd(a,n)|b，意思b是gcd(a,n)的倍数，这个
一下子也很难解释清楚啊，不满足这个条件，就是没解了。还有，如果有解的话，解的个数就是d = gcd(a,n)。而且其中一个解是x0 = x'(b
/ d)，其中x'是用扩展欧几里德算法求出来的，满足关系式a*x'+n*y'=d。
但是这个题不仅仅用到数论的这些知识，因为必须求满足条件的最小解，而如果有解的话是d个，而且满足解x = x0 + i(b/d)，
（1<=i<=d)。既然要求最小的解，那么对解mod(n/d)即可了，因为它们之间的差都是n/d的倍数。
代码如下：
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
//扩展欧几里德算法
//d = a * x + b * y，d是a和b的最大公约数
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的因子，然后取小的值肯定会超时的。
但是，我还是试了下，果断超时了。
那就只有想数学结论了，果断想到1-N中能被2整除的数字有N / 2。哈哈，再往后思考下，发现1-N中能被4整除的数字有N / 4个，再往后
就是N / 8，一直到N 除以2的某个次方为0为止，那么把所有的值加起来就是2的因子的个数了。求5的因子的个数也是这样的方法了。
很明显，5的因子的个数一定会小于等于2的因子的个数。那么直接求5的因子的个数就行了。由于，N / 5的时候用到了向下取整，
所以不能用等比数列求和公式，怎么把答案弄成一个公式，还不知道了。
PS：其实我这种思路的灵感来自于筛选素数的方法了。
代码如下：
#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;
}
这个题一看就知道是求欧拉函数。欧拉函数描述的正式题意。欧拉函数的理解可以按照算法导论上面的说法，对0-N-1进行筛选素数。
那么公式n
∏(1-1/p)，其中p是n的素数因子，就可以得到直观的理解了。但是计算的时候，会将这个式子变形下，得到另外一个形式。
如图所示：
但是这个题，需要考虑下，有可能n是个大素数，直接进行因子分解的话会超时的。怎么办了，只能在分解的时候判断n是不是已经成为
素数了，如果是素数，答案再乘以n-1就行了。为了加快判断，我用5mb的空间搞了个素数表，大于5000000的数字只能循环判断了。
代码如下，注意求欧拉函数的代码部分：
#include <stdio.h>
#include <math.h>
#define MAX (5000000)
bool bPrime[MAX];//false表示素数
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;
}