线性筛法求质因子的板子

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;}}}