010数论——算法备赛

数论

模运算

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

C/java	python
a>m,0<=a%m<=m-1 a<m,a%m=a	~
5%3==2	~
-5%3== -2	1
(-5)%(-3)== -2	~
5%(-3)==2	-1
正数：（a+b）%m==((a%m)+(b%m))%m	~
正数：（a-b）%m=((a%m)-(b%m))%m	~
(a*b)%m=((a%m)*(b%m))%m	~
an%m=(a%m)n % m	~

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	结果
true	true	-
true	false	+
false	true	+
false	false	-

可以看到，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);
}