數論
模運算
一般求余都是對正整數的操作，如果對負數，不同編程語言結果可能不同。
| 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);
}
函數解析)
