唯一分解式
2026-01-02 18:09:10
发布于：广东
7阅读
0回复
0点赞
2025年12月28日作业T4
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int a[N];
//1.记忆化 将我们需要求的答案给记住
int ans[N][N];
//ans[i][j];记录坐标[i,j]的答案(行走方案数),ans[i][j]
//a[i] ans[i]=a[i];
//2.状态转移方程 (已知状态和未知状态的转换关系)
//ans[i][j]=ans[i][j-1]+ans[i-1][j];
int main(){
int n,m;
cin>>n>>m;
ans[1][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans[i][j]=ans[i][j-1]+ans[i-1][j];
}
}
cout<<ans[n][m]<<endl;
}
唯一分解式 对于任何一个大于2的自然数,都可以分解为多个素数的乘积,且这个式子是唯一的
180 = 2^2 × 3^2 ×5
埃式筛
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
void solve(){
//埃式筛 sqrt(n);
//n*sqrt(n);
int n;//求n的唯一分解式子
queue<int>que;//队列 先进先出
//n分解最极端的情况 n是素数 两个素数的乘积
//25 5*5
//11
for(int i=2;i*i<=n;i++){//i*i<=n作用:跳过无用功
while(n%i==0){
que.push(i);
n/=i;
}
}
if(n>1)que.push(n);
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
线性筛
using namespace std;
const int N=1e8+10,M=1e6+10;;
#define ll long long
bool vis[N]; //对于vis[i]如果为true则表示为非素数,否则为素数
int prim[M];//记录素数
int top=0;//统计数量
//vis[i] a*b=i;非素数
void solve(){
//线性筛,对于任何一个大于1的自然数x
//都可以将其分解为一个最小质因子a,使得a*b=x;'
//60 2 2*30=60;
//25 5*5
int n,q;
cin>>n>>q;
//线性筛核心代码 算法复杂度为O(N)
for(int i=2;i<=n;i++){
if(vis[i]==0)prim[++top]=i;//如果当前的i不是素数,则将其记录
for(int j=1;j<=top&&i*prim[j]<=n;j++){ //i*prim[j]<=n防止越界
vis[i*prim[j]]=1;
if(i%prim[j]==0)break;
}
}
while(q--){
int k;
cin>>k;
cout<<prim[k]<<endl;
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
容斥定理
//a:1 2 3 4 5
//b:4 5 6 7 8
//a∪b 并集: 1 2 3 4 5 6 7 8
//容斥定理:求解并集
//a∩b 交集: 4 5
//【例】：有多少个能被3或5或7整除的小于等于1000的正整数？
//能被3整除的数字1000/3
//能被5整除的数字1000/5
//能被7整除的数字1000/7
//能被3,5整除的数字1000/(3*5);
//能被3,7整除的数字1000/(3*7);
//能被5,7整除的数字1000/(5*7);
//能被3,5,7整除的数字有1000/(3*5*7)
//A(3)+A(5)+A(7)-A(3,5) -A(3,7)-A(5,7)+A(3,5,7);
//给定n个数字
//每个数字的范围为1-(1e9)
//你可以进行两种操作中的任意一个操作
//1.选定一个a[i],将其*x(x为素数)
//2.选定一个a[i],将其/x(x为素数,且a[i]%x==0)
//问最少操作多少次可以将n个数字全都变成相同的
//唯一分解定理
//1 2 4 8 16
//0 1 2 3 4
这里空空如也
有帮助，赞一个