線性篩法求質因子的板子

int limit = 100000; //修改為題目中的數字的上限
bool isprime[100005] = {0}; //保存所有1~limit中的數字是不是質數
int myprime[100005] = {0};  //保存2~limit中所有數字的最小質因子
int primes[100000] = {0};   //保存所有1~limit中出現的質數
int tot = 0;                //1~limit中質數的總個數
//保存每一個下標為i的數字對應的質因子的種類個數
int scors[100005] = {0};
int init = [](){memset(isprime,1,sizeof(isprime));for(int i = 2;i<=limit;i++){if(isprime[i]){primes[tot++] = i;myprime[i] = i;}for(int j = 0;j<tot && primes[j]*i <= limit;j++){int val = primes[j];isprime[val*i] = 0;myprime[val*i] = val;if(i%val == 0){break;}}}//計算1e5內的所有質數分數for(int i = 2;i<=limit;i++){int j = i;int cnt = 0;while(j!=1){cnt++;int div = myprime[j];while(j%div == 0){j /= div;}}scors[i] = cnt;}return 0;
}();

快速冪

ll quickmul(ll a,ll b){if(b == 1){return a;}else{if(b % 2 == 0){ll tmp = quickmul(a,b/2);return tmp*tmp%mo;}else{ll tmp = quickmul(a,b/2);return ((tmp*tmp%mo)*a)%mo;}}}