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为例
利用幂次与二进制的关系 a11=a8*a2*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;
}
幂运算的结果往往是大数，一般会对其取模处理。更据模的性质，
an%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 * 105s由数字、'+'、'-'、'('、')'、和' '组成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 * 105s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开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);
}