章节 4. 数学
#J31401. 试除法判定质数
输入n个数，判断是否为质数。
枚举2~n/i，判断n是否能被i整除。因为约数必然是偶数，（特殊情况为中心数的平方为n，我们默认两个中心数）一半在中心数左边，一半在中心数右边，所以我们只需枚举n/i次。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,x;
void zs(int x){
for(int i=2;i<=x/i;i++){
if(x%i==0){
cout<<"No"<<endl;
return ;
}
}
cout<<"Yes"<<endl;
return ;
}
int main(){
cin>>n;
while(n--){
bool l=1;
cin>>x;
zs(x);
}
return 0;
}
#J31402. 分解质因数
枚举2~n/i，判断n是否能被i整除。如果n能被i整除，重复执行直到n=0,在循环中，我们使用cnt计数变量来记录n是i的几次饭。随后输出即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a;
cin>>n;
while(n--){
cin>>a;
for(int i=2;i*i<=a;i++){
if(a%i==0){
int x=0;
while(a%i==0){
a/=i;
x++;
}
cout<<i<<" "<<x<<endl;
}
}
if(a>1) cout<<a<<" 1"<<endl;
cout<<endl;
}
return 0;
}
#J31403. 筛质数
vector prime;
给定一个正整数n，求出1∼n中质数的个数。由于数字太多太大，所以我们可以使用质数筛来解。
我们可以使用标价数组来标记数的倍数,标记过的数子直接跳过便可以,我们将这种筛法称做朴素筛，这样便使得时间复杂度降O(n n)
朴素筛法代码：
const int N=1e6+5;
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for(int i=2; i<=n;i++) {
if(!st[i]) {
primes[++cnt]=i;
}
for (int j=i+i;j<=n;j+=i) st[j]=1;
}
}
使用朴素筛，我们成功的避免了每次判定质数的O(N)的时间复杂度，但是我们这样筛选依然有很多重复的数字一直在被筛选，所以我们还能在改进一下，使得时间复杂度降O($\sqrt{n} $)
埃氏筛法代码：
const int N=1e6+5;
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for (int i=2;i<=n;i++) {
if (!st[i]){
primes[++cnt]=i;
for(int j=i+i;j<=n;j+=i) st[j]=1;
}
}
}
题目代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int primes[N],cnt,n;
bool st[N];
void shai(int n) {
for (int i=2; i<=n; i++) {
if (!st[i]) {
primes[++cnt] = i;
for (int j=i+i; j<=n; j+=i) st[j] = 1;
}
}
}
int main() {
cin>>n;
shai(n);
cout<<cnt;
return 0;
}
#J31404. 试除法求约数
给定n个正整数ai对于每个整数ai请你按照从小到大的顺序输出它的所有约数。
这一题我也不知道该怎么写了合适，我就直接将我当时的思考过程写下了。
- 输入你n，随后读入a[i]
- 循环遍历至i>n/i。
- 如果n%i==0将i压入q数组中，进行一次判断，如果i！=a[i]/i,将a[i]/i压入q数组中（q为动态pair数组）。
- sort排序输出。
代码：
#include<bits/stdc++.h>
using namespace std;
vector<int> q;
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
for(int i=1;i<=x/i;i++)
if(x%i==0) {
q.push_back(i);
if(i!=x/i) q.push_back(x/i);
}
sort(q.begin(), q.end());
for(auto s : q) cout<<s<<" ";
cout<<endl;
q.clear();
}
return 0;
}
#J31407. 最大公约数
给定n对正整数 ai,bi求出每对数的最大公约数。
- 解放1.直接使用c++内置函数__gcd()，求出最大公约数
注意：
- ** 千万千万 **不要在比赛中使用__开头的c++内置函数 ，用了会爆0,一用一个不吱声
- 解法2.使用辗转相除法。
代码：
#include<bits/stdc++.h>
using namespace std;
int T;
int a,b;
int gcd(int a,int b) {
int r;
while(a%b!=0){
r=a%b;
a=b;
b=r;
}
return b;
}
int main(){
cin>>T;
while(T--){
cin>>a>>b;
cout<<gcd(a,b)<<endl;
}
return 0;
}
#182. 快速幂
快速幂，二进制取幂，是一个在
的时间内计算
的小技巧，而暴力的计算需要
的时间。
过程：
计数方法：
- 将b转换为二进制，先计数二进制位第一位数，随后根据数学的一些性质我们可以推出公式：当前项=前一项的平方。
- 计算二进制位数上为一的数字，随后累加起来%p得到答案
代码：
#include<bits/stdc++.h>
using namespace std;
long long a,b,p,ans=1;
int main(){
cin>>a>>b>>p;
while(b){
if(b & 1) ans=ans*a%p;
a=a*a%p;
b=b>>1;
}
cout<<ans%p<<endl;
return 0;
}
#J31409. 64位整数乘法
整体与快速幂一样，只是将一些乘法运算改为加法运算。
代码：
#include<bits/stdc++.h>
using namespace std;
long long a,b,p,ans;
int main() {
cin>>a>>b>>p;
while(b){
if(b & 1) ans=(ans+a)%p;
a=a*2ll%p;
b=b>>1;
}
cout<<ans%p<<endl;
return 0;
}
