这一次主要是数论专题，感到思维量比上一次的数学题要多多了。同样的问题也是英文题看起来有些吃力。
UVaOJ 575
这应该算不上是一个数论题，它重新定义了一种进制转换的公式，然后根据公式计算即可。
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
| #include <iostream>
using namespace std;
int Pow(int x, int y);
int main()
{
string x;
while(cin >> x)
{
if(x == "0") { break; }
int ans = 0;
for(int i = 0; i < x.length(); i++)
{ ans += (x[i] - '0') * (Pow(2, x.length() - i) - 1); }
cout << ans << endl;
}
return 0;
}
int Pow(int x, int y)
{
int ret = 1;
for(int i = 1; i <= y; i++)
{ ret *= x; }
return ret;
}
|
UVaOJ 10110
这是一道典型的数论题，最后亮着的灯，它的开关一定被拨动了奇数次。所以，我们只要看它的因数个数的奇偶性。
记得高中数学竞赛的时候遇到过类似的题目，有一个结论——完全平方数的因数有奇数个，非完全平方数的因数有偶数个。
这个命题的证明有些繁琐，读者自己思考一下就会发现，这个结论是正确的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <math.h>
using namespace std;
int main()
{
long long N;
while(cin >> N)
{
if(N == 0) { break; }
long long x = (long long)floor(sqrt(N * 1.0) + 0.5);
if(x * x == N) { cout << "yes" << endl; }
else { cout << "no" << endl; }
}
return 0;
}
|
UVaOJ 550
类似倒推的思想。
首先，我们有$B$、$D$、$M$ ——分别代表进制、最后一位数字、乘数。我们不妨记满足条件的数字为 $N$，且 $N \cdot M = S$。
有了上述假设，我们就可以进行如下操作：
$N$ 的最后一位数字为 $D$，那么 $S$ 的最后一位数字记为 $T = D \cdot M \mod B$（这里为 $B$ 进制）。
这时候需要注意的是，$S$ 的最后一位数字，恰好是 $N$ 的倒数第二位数字，那么也就是说 $N$ 的倒数第二位数字为 $T$。
有了 $N$ 的倒数第二位数字，我们就可以求出 $S$ 的倒数第二位数字为 $T\cdot M \mod B + T / B$（其中 $T / B$ 为进位），以此类推。
直到我们计算出来的数字与一开始给定的数字 $D$ 相当，这时候的 $N$ 的位数即为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
using namespace std;
int main()
{
int B, D, M;
while(cin >> B >> D >> M)
{
int nCnt = 1;
int nD = D;
while((nD = M * (nD % B) + (nD / B)) && nD != D)
{ nCnt++; }
cout << nCnt << endl;
}
return 0;
}
|
UVaOJ 568
由于数据范围比较小，我们可以直接算出来，记得在每次计算的时候把末尾的 0 去掉，同时为了防止溢出，我们可以对 10 的一个幂次取模。
这里选择了 10000，因为最大的 $N$ 为 10000。但是这个选取并不是任意的，比如我们取 10，计算出来的结果就会出错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <iomanip>
using namespace std;
const int MAX = 100000;
int main()
{
int N;
while(cin >> N)
{
int ans = 1;
for(int i = 1; i <= N; i++)
{
ans *= i;
while(ans % 10 == 0) { ans /= 10; }
ans %= MAX;
}
cout << setw(5) << N << " -> " << ans % 10 << endl;
}
}
|
UVaOJ 408
这道题目就是求满足 $$\mathrm{seed}(x + 1) = [\mathrm{seed}(x) + \mathrm{STEP}] \mod \mathrm{MOD}$$ 的 $\mathrm{seed}(x)$ 能否组成模 $\mathrm{MOD}$ 的剩余系。
有一个结论，若 $\mathrm{gcd}(\mathrm{STEP}, \mathrm{MOD}) = 1$，则可以组成一个模 $\mathrm{MOD}$ 的剩余系。
我们可以这样来证明：
$$\begin{align*}\mathrm{seed}(x + 1) &= [\mathrm{seed}(x) + \mathrm{STEP}] \mod \mathrm{MOD} \\ &= [\mathrm{seed}(x - 1) + 2 \cdot \mathrm{STEP}] \mod \mathrm{MOD} \\ &= [\mathrm{seed}(x - 2) + 3 \cdot \mathrm{STEP}] \mod \mathrm{MOD} \\ &= \cdots \\ &= [\mathrm{seed}(0) + (x + 1) \cdot \mathrm{STEP}] \mod \mathrm{MOD}\end{align*}$$
若不能满足条件，则必定存在 $0 \leq i \neq j < \mathrm{MOD}$ 的整数 $i$ 和 $j$ 满足：$\mathrm{seed}(i) = \mathrm{seed}(j)$，即 $$[\mathrm{seed}(0) + i \cdot \mathrm{STEP}] \mod \mathrm{MOD} = [\mathrm{seed}(0) +j \cdot \mathrm{STEP}] \mod \mathrm{MOD}$$ 即 $$((j - i) \cdot \mathrm{STEP}) \mod \mathrm{MOD} = 0$$ 又 $j - i < \mathrm{MOD}$，所以 $\mathrm{gcd}(\mathrm{STEP}, \mathrm{MOD}) \neq 1$，即 $ \mathrm{STEP} $ 中含有 $\mathrm{MOD}$ 的因子——若 $\mathrm{MOD}$ 整除 $j - i$，那么 $\mathrm{STEP}$ 中含有 $\mathrm{MOD}$ 的因子 $\mathrm{MOD} / (j - i)$，反之，$\mathrm{STEP}$ 含有因子 $\mathrm{MOD}$。
故需满足题设条件，必有 $$\mathrm{gcd}(\mathrm{STEP}, \mathrm{MOD}) = 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
| #include <iostream>
#include <iomanip>
using namespace std;
int gcd(int x, int y);
int main()
{
int x, y;
while(cin >> x >> y)
{
if(gcd(x, y) == 1) { cout << setw(10) << x << setw(10) << y << " Good Choice" << endl; }
else { cout << setw(10) << x << setw(10) << y << " Bad Choice" << endl; }
cout << endl;
}
return 0;
}
int gcd(int x, int y)
{
if(y == 0) { return x; }
else { return gcd(y, x % y); }
}
|
UVaOJ 350
简单模拟，没有想到数论的做法。不断的计算 $L$，直到发现重复。
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
| #include <iostream>
#include <memory.h>
using namespace std;
const int MAX = 10240;
int f[MAX];
int main()
{
int nCase = 0;
int Z, I, M, L;
while(cin >> Z >> I >> M >> L)
{
if(Z == 0 && I == 0 && M == 0 && L == 0) { break; }
int nCnt = -1;
memset(f, 0, sizeof(f));
do
{
L = ((Z % M) * (L % M) + (I % M)) % M;
f[L]++;
nCnt++;
}
while(f[L] == 1);
cout << "Case " << ++nCase << ": " << nCnt << endl;
}
return 0;
}
|
UVaOJ 10061
要求 $N!$ 转化为 $B$ 进制后的位数以及末尾 0 的个数。
为了简化问题，我们首先来看 10 进制的情况。
我们知道，在 10 进制情况下，我们有 $$f(N) = f(N / 5) + N / 5$$
证明：令 $k = N / 5$，则 $$N! = 5k \cdot 5(k - 1) \cdot \cdots \cdot 10 \cdot 5 \cdot a = 5^k \cdot k! \cdot a$$ 其中 $a$ 为不能被 5 整除的部分。因此， $$f(N) = f(k) + k = f(N / 5) + N / 5$$ 证毕。
有了上面的结论，我们可以大胆猜测，对于 $B$ 进制数，我们有 $$f(N, B) = f(N / X, B) + N / X$$ 其中 $X$ 为 $B$ 的最大因数，证略。
这样，我们就解决了第一个问题，对于第二个问题，我们可以直接取对数，计算 $\log{\left(N!\right)}$，即 $$\log{1} + \log{2} + \log{3} + \cdots + \log{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
| #include <iostream>
#include <math.h>
using namespace std;
const int MAX = 1 << 20;
double pLog[MAX];
int main()
{
for(int i = 1; i < MAX; i++)
{ pLog[i] = pLog[i - 1] + log(i); }
int N, B;
while(cin >> N >> B)
{
int nLen = (int)floor(pLog[N] / log(B) + 1E-9) + 1;
int nMaxFactor, nFactorCnt = 0, nCnt = 0;
for(int i = 2; i <= B; i++)
{
nFactorCnt = 0;
while(B % i == 0)
{
nMaxFactor = i;
nFactorCnt++;
B /= i;
}
}
while(N)
{
N /= nMaxFactor;
nCnt += N;
}
cout << nCnt / nFactorCnt << " " << nLen << endl;
}
return 0;
}
|
UVaOJ 10392
质因数分解即可，要注意题目中说只有一个大于 1,000,000 的因子，但是还是需要处理本身就是素数以及除到最后不等于 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
| #include <iostream>
#include <memory.h>
#include <vector>
using namespace std;
const int MAX = 1000020;
vector<int> pVec;
bool pVisited[MAX];
int main()
{
memset(pVisited, false, sizeof(pVisited));
for(int i = 2; i < MAX; i++)
{
if(!pVisited[i]) { pVec.push_back(i); }
for(int j = i + i; j < MAX; j += i)
{ pVisited[j] = true; }
}
long long N;
while(cin >> N)
{
if(N < 0) { break; }
int nCnt = 0;
for(int i = 0; i < pVec.size(); i++)
{
if(N < pVec[i]) { break; }
while(N % pVec[i] == 0)
{
cout << " " << pVec[i] << endl;
N /= pVec[i];
nCnt++;
}
}
if(nCnt == 0 || N != 1) { cout << " " << N << endl; }
cout << endl;
}
return 0;
}
|
UVaOJ 10879
这道题目的样例好像有点吓唬人，其实里面应该有 spj 的。
数据量不大，直接分解因式即可。
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
| #include <iostream>
using namespace std;
int main()
{
int T, N;
cin >> T;
for(int i = 1; i <= T; i++)
{
cin >> N;
cout << "Case #" << i << ": " << N;
int nCnt = 0;
for(int j = 2; j * j <= N; j++)
{
if(N % j == 0)
{
cout << " = " << j << " * " << N / j;
nCnt++;
}
if(nCnt == 2) { break; }
}
cout << endl;
}
return 0;
}
|
数论专题很多都是看着题解做的，因为很多都不知道，学到了很多新的东西。