010数论——算法备赛

数论

模运算

一般求余都是对正整数的操作，如果对负数，不同编程语言结果可能不同。

C/java：负数求余结果为非正数，正数求余结果为非负数，求余结果的绝对值为两数绝对值求余的结果。

python：若余数m为正数，求余结果范围[0,m-1]，若余数m为负数，求余结果范围[m+1,0]

乘法取模公式需注意：两个大数a*b可能溢出。

以下代码在一定程度上可以解决

typedef long long ll;
ll mul(ll a,ll b,ll m){
    a%=m;
    b%=m;
    ll res=0;
    while(b>0){  //以空间换时间
        if(b&1) res=(res+a)%m;
        a=(a<<1)%m;  //需保证2a不会溢出 a>m;
        b>>=1;
    }
    return res;
}

为了不直接计算 a*b ，改为计算（a*2)*(b/2)

即为求**（a*2)*(b/2)%m ={(（a*2)%m )*(b/2)}%m**。每次将（a*2)%m 赋值给a；

连续执行 a*2和b/2

即（a*2*2…*2）*(b/2/2…/2),

直到b减少为1，原式改为求 （a*2*2…*2）%m

当b减少为0时，循环结束，返回目标值res。

当b为偶数时 a*b ==（a*2)*(b/2)

当b为奇数时 a*b ==（a*2)*(b/2)+a 每次将多出来的a求余存进res。

最大公约数

递归写法

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

动态规划写法

while(b > 0){
    int tmp = a % b;
    a = b;
    b = tmp;
}
return a;

最小公倍数

int lcm(int a,int b){
    return a*b/gcd(a,b);
}

快速幂

对于a^n 如果一个一个地乘，计算量为O(n),采用快速幂计算，计算量为O(log2n);

以a^11为例

利用幂次与二进制的关系 a^11=a8*a^2*a1;

ll fastPow(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)  ans*=a;
        a*=a;  //倍增递推 a  a^2  a^4  a^8 ...
        n>>=1;  //右移，把处理过的n的最后一位去掉
    }
    return ans;
}

幂运算的结果往往是大数，一般会对其取模处理。更据模的性质，

a^n%m=(a%m)n % m.

上述代码修改为

ll fastPow(ll a,ll n,ll m){
    ll ans=1;
    a%=m;  //一定程度上能防止溢出。，但做题时仍需谨慎，a不能太大，否则只能用高精度处理。
    while(n){
        if(n&1) ans=(ans*a)%m;
        a=(a*a)%m;
        n>>=1;
    }
}

上述代码依然存在溢出问题。 ans*a a*a可能溢出

计算 a^n%m ，如果n极大 如 n=10^200000000, 可以用“欧拉降幂”的方法。

统计好数字的数目

问题描述

我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。

• 比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是 好数字，因为 3 在偶数下标处但不是偶数。

给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。

一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

原题链接

代码

int countGoodNumbers(long long n) {
        int mod=1e9+7;
        long long t4=n/2,t5=(n+1)/2;
        auto pows=[&](long long s,long long t)->long long{  //快速幂
            long long ans=1;
            while(t){
                if(t&1) ans=(ans*s)%mod;
                s=(s*s)%mod;
                t>>=1;
            }
            return ans;
        };
        return (pows(4,t4)*pows(5,t5))%mod;
    }

字符串表达式运算

基本计算器|

问题描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

提示：

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• ‘+’ 不能用作一元运算(例如， “+1” 和 "+(2 + 3)" 无效)
• ‘-’ 可以用作一元运算(即 “-1” 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

原题链接

思路分析

首先考虑如果没有括号的情况，那就是简单的加减运算，有了括号问题就变得复杂一点，借助小学的知识去除括号，那问题就变成简单的加减题。

• 括号左边运算符为+,那直接去除，例1+(2+3)——>1+2+3
• 括号左边运算符为-,那去除括号后，括号内的运算符全部反转,例1-(2+3)——>1-2-3

对于嵌套的反转其实就是反转后再反转。

定义oper指示前一个运算符是+(true),还是减-(false)

定义rev指示括号内运算符是否反转，每遍历到一个'('就决定是否对rev取反，遍历到')'就取消决定，这里为应对多重的()，用一个栈来维护前面的决定。

对于oper,rev的值对数值的运算有如下关系：

可以看到，oper与rev的共同作用对加还是减运算其实是异或的结果，oper^rev为true，则做加法，oper^rev为false，则做减法。

代码

int calculate(string s) {
    int n = s.size();
    int ans = 0, pre = 0;
    bool oper = true, rev = false;
    stack<bool>st;
    for (int i = 0; i < n; i++) {
        if (s[i] == ' ') continue;
        switch (s[i]) {
        case '+':
            oper = true;
            break;
        case '-':
            oper = false;
            break;
        case '(':
            st.push(oper);
            if (!oper) rev = !rev,oper=true;
            break;
        case ')':
            if (!st.top()) rev = !rev;
            st.pop();
            break;
        default:
            pre=pre*10+(s[i]-'0');
            if(i==n-1||s[i+1]<'0'||s[i+1]>'9'){
                if (rev ^ oper) ans += pre;
                else ans -= pre;
                pre=0;
            }
        }
    }
    return ans;
}

基本计算器||

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

提示：

• 1 <= s.length <= 3 * 105
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

原题链接

代码

int calculate(string s) {
        int ans=0,pre=0,num=0,n=s.size();
        char preOper='+';
        bool isAdd=true;
        for(int i=0;i<=n;i++){
            if(i<n&&s[i]==' ') continue;
            if(i<n&&s[i]>='0'&&s[i]<='9'){
                num=10*num+(s[i]-'0');
            }else{
                switch(preOper){
                    case '*':
                        pre*=num;
                    break;
                    case '/': 
                        pre/=num;
                    break;
                    case '+':
                    case '-':
                        ans+=isAdd?pre:-pre;
                        pre=num;
                        isAdd=preOper=='+';
                    break;
                }
                if(i<n) preOper=s[i];
                num=0;
            }
        }
        ans+=isAdd?pre:-pre;
        return ans;
    }

数位统计

无理数位数查询

问题描述

原题链接

思路分析

见注释。

代码

#include <bits/stdc++.h>
#define IOSCC ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
typedef unsigned long long ll;
const int N = 1e6 + 10;

ll qpow(ll a,ll b){  //快速幂求a的b次方。
    ll res = 1;
    while(b){
        if(b & 1) res = res * a;
        b >>= 1;
        a = a * a;
    }
    return res;
}

void solve() {
    ll n, m;
    cin >> n >> m; 
    ll res = 0;
    ll i, j;
    for (i = m - 1, j = 1;; i *= m, j++) { //这一步是为了找到在位数为j时可以找到n的位数
        res += i * j;
        if (res >= n) {
            res -= i * j;
            break;  //直接退出，j不再加1、
        }
    }

    ll offset = n - res;  //得到从位数为j开始时的偏移量

    ll num = offset / j;  //target为j位数中的第num个。
    ll digit = offset % j;   //目标数字（数位）为目标数值中的第digit个数字
    if(digit == 0) num--,digit = j; //如果digit为0的话，说明要找的数是数值的最后一位

    ll target = qpow(m, j - 1) + num; //得到当前的数字

    string t1;  //数值可能很大，要用字符串储存。
    while (target) {
        t1 += ('0' + (target % m)); //用字符串存储m进制数target，从低位到高位
        target /= m;
    }
    reverse(t1.begin(), t1.end()); //翻转  将数值target用字符串表示出来（从高位到第位）。
    cout << t1[digit - 1];  //输出位数，因为字符串从0开始，所以减1
}

int main() {
    IOSCC;
    int _ = 1;
    cin >> _;

    while (_--) {
        solve();
        cout << endl;
    }

    return 0;
}

统计强大整数的数目

问题描述

给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。

如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。

请你返回区间 [start..finish] 内强大整数的 总数目 。

如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。

原题链接

代码

long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
    long long num=0,digs=1;  num为s表示的数值，digs=10^n(n为num的位数)
    for(int i=0;i<s.size();i++){
        num=num*10+s[i]-'0';
        digs*=10;  
    }
    auto numbers=[&](long long st)->long long{  //求[0,st]范围内的强大整数数目
        long long st_dig=st/digs,st_mod=st%digs,ans=0;
        long long power=1;
        int i=0;
        while(st_dig){
            int p=st_dig%10;
            if(p<=limit){
                ans+=p*power;  
                //最高位为p时，后面有些值可能取不到，组合总数继承上一个ans
                //最高位为[0,p-1]时,后面每位可取[0,limits],组合总数为p*power
                //总的组合数就是ans+p*power.
                if(!i&&st_mod>=num) ans++;  //第一位且st_mod>=num时，少算了一个,加上.
            }
            else{
                 ans=(limit+1)*power;
            }
            st_dig/=10;
            power*=limit+1; 
            i++;
        }
        if(st>=num&&ans==0) return 1;  //未进入循环，但st>=num,可以构成一个强大整数
        return ans;
    };
    return numbers(finish)-numbers(start-1);
}