做网站一月工资,深圳建站推广公司,网站备案正常多久,宁波商城网站开发设计板子 线性筛法求质因子的板子快速幂 线性筛法求质因子的板子
int limit 100000; //修改为题目中的数字的上限
bool isprime[100005] {0}; //保存所有1~limit中的数字是不是质数
int myprime[100005] {0}; //保存2~limit中所有数字的最小质因子
int primes[100000] {0}; … 板子 线性筛法求质因子的板子快速幂 线性筛法求质因子的板子
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;ilimit;i){if(isprime[i]){primes[tot] i;myprime[i] i;}for(int j 0;jtot 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;ilimit;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;}}}
