唯一式分解,容斥
2026-01-17 15:47:02
发布于：广东
11阅读
0回复
0点赞
//唯一分解定理(今年五级题编程题第二题考点)
//对于任意的一个大于1的自然数都可以表示为多个质因子相乘的形式
//比如180=>2*2*3*3*5=>(2^2)*(3^2)*5
//对于最终的式子(2^2)*(3^2)*5被称为唯一分解式
//唯一分解定理:对于满足条件的自然数都存在一个唯一的唯一分解式
//题目1:https://www.acgo.cn/problemset/info/7983?homeworkId=15377&teamCode=1989649572886384640
//样例拆解
//2^2*3*5
//2^2 -->>2*2
//3-->3^1 ->>3
//5-->5^1 ->>5
/*
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
void solve(){
int n;
cin>>n;
int flg=1;//标记是否第一次输出
string s;//存储答案
for(int i=2;i<=n;i++){
int cnt=0;//统计次数
while(n%i==0){
cnt++;
n/=i;
}
if(cnt){
if(cnt==1){
//to_string(i)将int类型转化为string
s+=to_string(i)+"*";
}
else{
s+=to_string(i)+"^"+to_string(cnt)+"*";
}
}
}
// cout<<s<<endl;
// s.substr(起点下标,截取长度)
cout<<s.substr(0,s.size()-1);
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
*/
//题目2:https://www.acgo.cn/problemset/info/7983?homeworkId=15377&teamCode=1989649572886384640
//题目要求:输出N!的质因子分解
//因为N!可能会非常非常大,所有题目可以拆解为求1-N中每个数字的质因子分解
//再将质因子分解的结果进行统计(计数--桶排)
// #include<bits/stdc++.h>
// using namespace std;
// const int N=2e5+10;
// #define ll long long
// int cnt[N];//计数统计
// void run(int x){//质因子分解函数 将x进行质因子分解
// for(int i=2;i<=x;i++){
// while(x%i==0){
// cnt[i]++;
// x/=i;
// }
// }
// }
// void solve(){
// int n;
// cin>>n;
// for(int i=1;i<=n;i++){
// run(i);
// }
// for(int i=2;i<=n;i++){
// if(cnt[i])cout<<i<<' '<<cnt[i]<<endl;
// }
// }
// int main(){
// int t=1;
// // cin>>t;
// while(t--){
// solve();
// }
// }
//中位数定理
//给定n个数字,你可以对其中任何一个数字进行+1或者-1操作
//要求将n个数字全都变成相同的最小操作次数
//结论:排序过后,取中间的数字x为基准,所有数字都操作为x
//奇数情况只有一个x,x即为操作数
//偶数情况有x1,x2; 区间[x1,x2]都可以作为操作数
//埃式筛
// bool check(int x){//判断x是否为素数,sqrt(x)*n 1e8数据情况下,1e8*1e4=1e12
// for(int i=2;i*i<x;i++){
// for(int i=2;i<=sqrt(x);i++){//不建议使用
// for(int i=2,len=sqrt(x);i<=len;i++){
// if(x%i==0){
// return false;
// }
// }
// return true;
// }
//线性筛 原理--->利用唯一分解
//对于最终的式子(2^2)*(3^2)*5被称为唯一分解
//将x唯一分解式子转化为一个最小质因子的乘积形式,
//假设最小质因子为a x=a*x/a;
//180 --->2*90;
// #include<bits/stdc++.h>
// using namespace std;
// const int N=1e8+10,M=1e7+10;
// #define ll long long
// bool a[N];//如果a[i]=true;则表示i为非质数,否则为质数
// int p[M],top=0;//存储答案
// void prim(int n){//计算出1-n的所有质数
// for(int i=2;i<=n;i++){
// if(a[i]==0){
// p[top++]=i;//存储质数
// }
// for(int j=0;j<top&&p[j]*i<=n;j++){
// a[p[j]*i]=true;//对于所有最小质因子的乘积进行标记
// if(i%p[j]==0)break;
// }
// }
// }
// void solve(){
// int n,q;
// cin>>n>>q;
// prim(n);
// while(q--){
// int k;
// cin>>k;
// cout<<p[k-1]<<endl;
// }
// }
// int main(){
// int t=1;
// // cin>>t;
// while(t--){
// solve();
// }
// }
//集合:{1,2,3}
//元素:对于集合{1,2,3}中的元素为1,2,3
//交集∩ 相交部分的集合 对于集合{1,2,3}和集合{3,4,5} {1,2,3}∩{3,4,5}={3}
//并集∪ 合并部分的集合 对于集合{1,2,3}和集合{3,4,5} {1,2,3}∩{3,4,5}={1,2,3,4,5}
//{1}+{1}={1,1};
//A={1,2,3},B={3,4,5};
//{1,2,3}∩{3,4,5}=A+B -->{1,2,3,3,4,5}
//-A∩B-->{3};
//=AUB
这里空空如也
有帮助，赞一个