海口网站制作案例,江宁区建设工程局网站进不去,wordpress怎么做响应式网站,微营销软件文章目录
目录
文章目录
前言
一、数论有哪些
二、题法混讲
1.素数判断,质数,筛法
2.最大公约数和最小公倍数
3.快速幂
4.约数 前言
现在针对CSP-J/S组的第一题主要都是数论,换句话说,持数论之剑,可行天下矣! 一、数论有哪些
数论 原根,素数判断,质数,筛法最大公约数…文章目录
目录
文章目录
前言
一、数论有哪些
二、题法混讲
1.素数判断,质数,筛法
2.最大公约数和最小公倍数
3.快速幂
4.约数 前言
现在针对CSP-J/S组的第一题主要都是数论,换句话说,持数论之剑,可行天下矣! 一、数论有哪些
数论 原根,素数判断,质数,筛法最大公约数,gcd扩展欧几里德算法,快速幂,exgcd,不定方程,进制,中国剩余定理,CRT,莫比乌斯反演,逆元,Lucas 定理,类欧几里得算法,调和级数,欧拉降幂......
但是,可但是,但可是,我是个蒟蒻,只能胜任很简单的数论和算法,今天只是做个考前复习罢了
二、题法混讲
1.素数判断,质数,筛法
(1)素数,质数的定义:只能被一和他本身整除的正整数教素数,又称质数(2是素数,0和1却不是)
(2)判定 代码如下示例 bool isprime(int n){if(n2) return false;int xsqrt(n);for(int i2;ix;i)if(n%i0) return false;return true;
}
(3)埃氏筛 代码如下示例 void get_primes(int n){for(int i2;in;i){if(!flag[i]){p[cnt]i; for(int j1;p[j]n/i;j){flag[p[j]*i]true;}}}
}
(4)线性筛 代码如下示例 void get_primes(int n){for(int i2;in;i){if(!flag[i]){p[cnt]i;for(int j1;p[j]n/i;j){flag[p[j]*i]true;if(i%p[j]0) break;}}}
} 2.最大公约数和最小公倍数
代码如下示例
int gcd(int x,int y){if(y0) return x;return gcd(y,x%y);
}
int lcm(int x,int y){return x*y/gcd(x,y);
}
3.快速幂
递归写法:
int ksm(int a,int b,int mod){if(!b) return 1;int tksm(a,b1,mod);return (LL)(b1?a:1)*t%mod*t%mod;
}
非递归写法:
①
int ksm(int a,int b,int mod){int res1;while(b){if(b1) res(LL)res*a%mod;aa*a%mod;b1;}return res;
}
②
int ksm(int a,int b,int mod){int ans1;for(;b;a*a,a%mod,b1)if(b1) ans*a,ans%mod;return ans;
}
4.约数
代码如下(实例):
vectorint d;
void solve(int n){d.clear();for(int i 1; i n / i; i ){if(n % i 0){d.push_back(i);if(i ! n / i) d.push_back(n / i);}}sort(d.begin(), d.end());for(auto x : d) cout x ;
} 祝大家CSP-J/S,RP
