数论

2021-01-02

数论

1. Leftmost Digit

杭电1060题，给你一个数字$n$，求出$n^n$最高位数字$t$，$n$不超过$10,000,000,000$(10亿)。

具体思想如下：

设$M = n^n$（n为整数），两边取10的对数则有

$\log_{10}M = \log_{10} n^n = k$

直觉上，如果$M$不是10的整数幂次，那么$k$是一个浮点数。

$k = A.B$

$A$为$k$ 的整数部分，$B$ 则为$k$ 的小数部分。有

$\log_{10} M = k = A.B \\ 10^{A.B} = M \\ 10^A*10^{B} = M(B < 1)$

其实$A$就代表了$M$的位数（三位数$10^2$、四位数$10^3$以此类推），而$10^B$相当于前面的系数（有点类似科学计数法那个形式）。

我们观察幂函数$y = 10^x$ ，在$x = 1$时$y = 10$，我们这儿$B < 1$，因此$10^B$的值介于$[1,10)$之间，并且是一个浮点数。我们可以这么想，$10^A*10^{B}$把$10^B$放大了$10^A$倍后得到了$M$，即 $n$ 的 $n$ 次幂。

好了，那么$M$的最高位到底是几？很明显是$10^B$这个数字的整数部分。如何取到$B$这个小数呢，$k = n \log_{10} n = A.B$，$k$减去其取整部分即可得到$B$。$10^B$再取整就得到了最高位。

程序代码如下

#include<stdio.h>
#include<math.h>
#include <iostream>
using namespace std;
int main()
{
	int t,n;
	double k;
	scanf("%d",&t);
	for(int i = 0; i < t; i++){
        scanf("%d",&n);
        k = n * log10(1.0 * n); // k = A.B
        // k减去对k取整部分得到小数部分
        k = k - (__int64)k;
        printf("%d\n",(int)pow(10,k));

	}
	return 0;
}

2. Euler函数

在数论中，对正整数，欧拉函数是小于或等于n的正整数中与n互质的数的数目。比如$\phi(8) = 4$，因为1、3、5、7与8互质。注：互质为两者没有除1外的公因数。

具体定义如下：

我们知道，对于任意正整数n，都可以表示为多个质数的乘积，即如下形式：

$n = p_1^{k_1}p_2^{k2}...p_n^{k_n}$

，其中，$p_i$均为质数。

那么欧拉函数$\phi(n)$等于

$\phi(n) = n\prod_{i=1}^n (1 - \frac{1}{p_i})$

性质：

① 欧拉函数是积性函数，$\phi(mn)=\phi(m)*\phi(n)$

② 若p为质数，$\phi(p)=p-1$

#include<stdio.h>
#include<math.h>
using namespace std;
// 欧拉函数:统计小于等于n中与n互质的数的个数
int euler(int n){
    int ans = n;
    int tmp = n;
    // n在循环过程中会不断发生变化。
    for(int i = 2; i <= sqrt(1.0 * tmp); i++ ){//枚举所有能够被n整除的质因数
        if(n % i == 0){
            ans = ans * (i - 1) / i;// 欧拉公式，不断累乘
            while(n % i == 0){
                n /= i; // 消除质数因子的过程
                //将质数i不断的左除过去
            }
        }
         // 新的n = n / p1 / p1 / p1 ... = p2*p2*p2...*pn
        // p1 < p2 < ... < pn
        // 再次循环通过枚举找到p2....pn

    }
    // n不为1，表明还有因子，最后一个质因子可能不在[2,sqrt(n)]之间
    if(n > 1){
        ans = ans / n * (n - 1);
    }
    return ans;
}

int main()
{
    int t,n;
    scanf("%d",&t);
    for(int i = 0; i < t; i++){
        scanf("%d",&n);

        printf("%d\n",euler(n));
    }
    return 0;
}

3. 找出缺失的数字

题目大意如下，首先输入$n$个不同的数字，再次输入$n-1$个数字，找出第二次输入没有输入的那个数字。输入的数字的值介于$[0,1000000000]$，$2 <= n <= 400000$。

可以看到数据规模较大，无论是集合还是利用高斯公式求两次和都可能数据溢出。能不能使用$O(n)$时间复杂度以及$O(1)$空间解决这个问题？

下面介绍二进制中异或（^）的操作的一些性质。

异或就是相同为0，不同为1。即1 ^ 1 = 0,0 ^ 0 = 0,1 ^ 0 = 1,0 ^ 1 = 1。异或还有如下性质

0 ^ x = x
x ^ x = 0
异或满足交换律，即1 ^ 2 ^ 4 ^ 6 = 6 ^ 2 ^ 1 ^ 4

有了这些性质，对于这个题，我们设置a = 0,b = 0；

a = a ^ arr1[i], i from 0 to n-1，b = b ^ arr2[j], j from 0 to n-2。

最后所求数字即为a^b。

其实很好理解：
$a = a_1 \bigoplus a_2 \bigoplus....\bigoplus a_n \\ b = b_1 \bigoplus b_2 \bigoplus....\bigoplus b_{n-1} \\$
最后a^b，由异或交换律这个性质等价于，将前后两次相同的数字先做异或得到0，前后两次相同的数字就都被消掉了，最后剩下的那个数字再与0异或还是这个数字，也就是第二次没有出现的那个数字。

同理，找出在都是偶数次出现的数字中出现次数为奇数次的数字也可以利用异或算法解决。

a = 1 ^ 2 ^ 4 ^ 6;b = 4 ^ 6 ^ 1;

a ^ b =1 ^ 2 ^ 4 ^ 6 ^ 4 ^ 6 ^ 1 = 1 ^ 1 ^ 4 ^ 4 ^ 6 ^ 6 ^ 2= 0 ^ 0 ^ 0 ^ 2 = 0 ^ 2 = 2

4. Rightmost Digit

杭电1061题。与第1题相反的是，本题求正整数$n^n$最左边的数字。要用到快速幂取模算法。快速幂即比较快的计算n的幂次。相比于循环n次计算的$O(n)$算法，快速幂能够在$O(\log n)$求出结果。比如计算$3^{100}$，一般我们可以循环100次计算出结果。

long long ans = 1;
for(int i = 1; i <= 100; i++){
    ans *= 3;
}

我们观察发现:

$3^{100} = 3^{50}*3^{50}\\ 3^{50} = 3^{25}*3^{25}\\ 3^{25} = 3^{12}*3^{12}*3\\ 3^{12} = 3^6*3^6 \\ 3^6 = 3^3*3^3\\ 3^3 = 3^2 * 3\\ 3^2 = 3 * 3$

这样，我们要计算$3^{100}$，就可以先计算出$3^{50}$，然后自己和自己相乘就可以得到结果，对于$3^{25}$同理，然后这样递推下去就可得到结果。按照这个方法计算，我们只做了8次乘法便得到了结果，相比100次大大减少了时间。幂次不是奇数就是偶数，偶数次幂就等于自己乘自己，奇数次幂得额外再乘以一个基底数字。

// 递归计算快速幂 a^b
int f(int a, int b){
    if(b == 1){
        return a;
    }
    int temp = f(a, b / 2);
    return (b % 2 == 0 ? 1 : a) * temp * temp;
}
// 非递归
int f(int a, int b){
    int base = a;
    int ans = 1;
    while( b != 0){
        if(b % 2 == 1){
            ans = ans * base;
        }
        base = base * base;
        b /= 2;
    }
    return ans;
}

回到这道题，两个数相乘，二者的最后一位分别相乘贡献了结果，因此我们可以在计算快速幂过程中不断对10取模就可以得到最终结果。

插入一点其他知识：

$(a + b) \mod p = (a\mod p + b \mod p) \mod p$

在计算斐波那契数列时会用到。将加号改为乘号同样适用。

#include <iostream>
#include <stdio.h>
using namespace std;

// 快速幂取余
int f(int a, int b){
    int base = a;
    int ans = 1;
    while( b != 0){
        if(b % 2 == 1){
            // 最后两位数相乘再对10取余 ans = ans * base ans % 10 = (ans%10)*(base%10)%10
            ans = (ans % 10) * (base % 10) % 10;
        }
        // 因为求最后一位数字，每次记录最后一位数字是几就可以避免越界
        base = (base % 10)* (base % 10) % 10;
        b /= 2;
    }
    return ans;
}
int main()
{
    int t,n;
    cin >> t;
    for(int i = 0; i < t; i++){
        scanf("%d",&n);
        printf("%d\n",f(n,n));
    }
    return 0;
}

5. 阶乘位数

给定一个小于等于$10,000,000$的正整数，计算其阶乘的位数。小于1000的数字的阶乘可以通过模拟乘法来计算出来，但是当数字特别大数组也无法存下。这是就要用到斯特林公式。

一个十进制数 $n$ 的位数可以表示为：

$(int)\log_{10} n + 1$

这一点可以很明显的在$y = \log_{10} x$的函数图像上观察出来。

因此，$n!$的位数即：

$\log_{10} n! + 1$ $\log_{10} n! = \log_{10} n * (n-1) * ... * 1 = \log_{10}n + \log_{10}n-1 + ...$

只要循环计算1到n的对数再求和之后取整加一就是结果。

6. 埃氏筛

给定正整数 $n$，输出小于 $n$ 的数中质数的个数。

class Solution {
    public int countPrimes(int n) {
        if (n <= 1){
            return 0;
        }
        // 素数的埃氏筛
        int cnt = 0, k = (int) Math.sqrt(n);
        boolean flag[] = new boolean[n];
        for (int i = 2; i <= k; i++){//注意 i 的最大值
            if (!flag[i]){
                for (int j = i * i; j < n; j += i){
                    flag[j] = true;
                }
            }
        }
        for (int i = 2; i < n; i++){// 注意 i 的最大值
            if (!flag[i]){
                cnt++;
            }
        }
        return cnt;
    }
}