7/21日课堂总结
知识点
唯一分解定理
唯一分解定理：任何一个大于1的整数，可以唯一拆分为若干个质因子的乘积。
质因子：本身就是质数的因子。
for(int i = 2; i * i <= n; i++)
if( !(n % i))
{
sum += i;
if(i*i!=n)
sum+=n/i;
}
$$
h=p1 ^ k1 * p2^k2 * p3k3*p4k4*...pm^km
$$
p[i]代表不同的质因子
唯一分解定理引理：一个整数x最多存在一个大于√x的质因子。
for(long long i = 2; i * i <= x; i++)//从最小的质因子开始（ll不要乱开，会影响时间）
while(!(x % i))
cout << i << ' ',x /= i;//说明i是一个质因子
if(x != 1)
cout << x << ' ';//还剩下空格
数学公式
$$
d | n==n%d
$$
d|n：代表n能被d整除。
n%d：判断一个数字n是否能被d整除。
n和d都能够进行唯一分触：
-
n分解的质因子种类包含，d分解所有的质因子种类。
-
d包含的所有质因子的出现次数，小于等于n对应的质因子的出现次数
$$
(ab)c==a(bc)==(p1(k1)...pm(km))==p1(nc)...pn((km)^2)
$$
习题
B3715 分解质因子 2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define le length()
typedef long long ll;
void solve()
{
ll n;
cin>>n;
if(n<=1)
return ;
for(ll i=2;i*i<=n;i++)
while(n%i==0)
{
cout<<i<<' ';
n/=i;
}
if(n!=1)
{
cout<<n<<'\n';
return ;
}
cout<<'\n';
return ;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin>>T;
while(T--)
solve();
return 0;
}
B2138 最大质因子序列
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define le length()
typedef long long ll;
int f(int x)
{
int maxx=-1;
for(int i=2;i*i<=x;i++)
while(!(x%i))
maxx=max(maxx,i),x/=i;
if(x!=1)
maxx=max(maxx,x);
return maxx;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n,m;
cin>>n>>m;
fo(i,n,m-1)
cout<<f(i)<<',';
cout<<f(m);
return 0;
}
P10495 阶乘分解 ||P2043 质因子分解
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define le length()
typedef int ll;
map<ll,ll> q;
void solve(ll n)
{
for(ll i=2;i*i<=n;i++)
while(n%i==0)
n/=i,q[i]++;
if(n!=1)
q[n]++;
return ;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin>>n;
for(int i=2;i<=n;i++)
solve(i);
for(int i=2;i<=n;i++)
if(q[i])
cout<<i<<' '<<q[i]<<'\n';
return 0;
}