2026年7月2日 - 数论 - 课堂笔
2026-07-02 16:53:28
发布于：广东
//二分
//二进制 10 >1010--->8+2
//100
//1 2 4 8 16 32 64 128
//100=64+32+4
// 1 1 0 0 1 0 0
//二分的前提一定具有单调性(二分查找，二分答案)
//1 4 7 10 14 21 32 40
//1 2 3 4 5 6 7 8
//7 lower_bound() upper_bound()
//倍增---->st表
//7 =1+2+4
//查找14所在的位置 -->5; -->8;
//1 2 4 8
//8-->大了，不取
//4-->小了，取
//2-->4+2(拿到6的位置)大了，不取
//1-->4+1(拿到5的位置)小于且等于，拿
//最终得到查找位置5=1+4;
//快速幂-->二进制拆解+倍增
//a^b%mod //取余(a+b)%mod<=>(a%mod+b%mod)%mod;+*-
//除法不具有分配律 (a/b)%mod!=(a%mod/b%mod)%mod;
//2^10=1+1+...+1(10个1) =>2+8;
//2^10=2^8*2^2
//2^1 2^2 2^4 2^8
//2 4 16 256//tmp
//tmp
//4*256=1024
ll power(ll a,ll b,ll mod){//a^b%mod;
ll tmp=a;//对应a^1;
ll inx=0;//对应当前次方a^(2^inx) 二进制拆解之后的第几位
ll ans=1;//保存最终的结果
while(b){//将b进行二进制拆解
// if((b>>inx)&1)//判断二进制情况下第inx位的0/1状态
if(b&(1LL<<inx)){
ans*=tmp;//
ans%=mod;//及时求mod，防止计算过程中炸ll
b-=(1LL<<inx);//减去拆解出来的二进制位
}
inx++;//继续往后
tmp*=tmp;//自身快速倍增
tmp%=mod;//
}
return ans;
}
//素数/合数
//快速幂 --(埃氏筛，线性筛)
//x
int is_prime(int x){
for(int i=2;i<x;i++){//O(x);
if(x%i==0)return false;
}
return true;
}
//优化方案
int is_prime(int x){
// for(int i=2;i<=sqrt(x);i++){//O(sqrt(x));
for(int i=2;i*i<=x;i++){//更快 sqrt(x);
if(x%i==0)return false;
}
return true;
}
//1-n
//埃氏筛时间复杂度nloglog
//(求1-n里面的所有素数，必须从小位置到大位置推导)
for(int i=2;i<=n;i++){//nsqrt(n) //nlog //nloglog
if(is_prime(i)){
vector.push_back(i);
}
}
//为什么只需要判断到sqrt(x)的范围内就可以得出是否是素数
// 合数
//x是合数
//6=2*3;
//x最少拆解成多少个素数相乘（最少拆解为两个）
//问拆解的所有素数当中，最小的那个最大可能是多少？
//21=3*7（最小的为3）
//对于任何的合数x，最小素数因子最大可能是多少？(sqrt(x));
//纯暴力方案
ll run(ll x){
ll sum=0;
for(int i=1;i<x;i++){
if(x%i==0)sum+=i;
}
return sum;
}
//
//s(28)=1+2+4+7+14+28=28。
//9 =1 3 9;
//优化
ll run(ll n){
ll sum=0;
if(n==1)return 0;
for(int i=2;i*i<=n;i++){
if(x%i==0){
sum+=i;
if(i!=x/i){
sum+=x/i;
}
}
}
return 0;
}
//1e9;
//动态规划
//1.记忆化
//2.状态转移方程
// int f[N];-->f[i] 第i项的答案
// f[i]=f[i-1]+f[i-2];//已知和未知的关系转化
// ans[N]//ans[i]表示i的答案
//i数字,j因数
// ans[i*j]+=j;
题目链接：https://www.luogu.com.cn/problem/P15930?contestId=334554
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define ll long long
ll a[N];
int main(){
for(int i=1;i<N;i++)
for(int j=2;i*j<N;j++){//nlog
a[i*j]+=i;
}
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
// cout<<x<<' '<<a[x]<<endl;
if(a[x]>x)cout<<"abundant"<<endl;
if(a[x]<x)cout<<"deficient"<<endl;
if(a[x]==x)cout<<"perfect"<<endl;
}
}
//唯一分解定理
//对于任何一个数字都可以拆解成一个唯一的素数乘积形式
//60=2*2*3*5 （唯一的数字可以拆解为唯一的式子）
// （唯一的式子对应唯一的一个数字）
//1 2 1 1 1 1
//2 4 4 4 2 2 //最少操作三次即可，将所有的2*2
//1 2 2 2 1 1 //将乘法除法 转化为+1/-1操作
//
//1 2 3 4 5 6 //拆解素数因子
// 3 4//中位数定理 对于一个数组如果可以对数组中任何一个数字进行+1/-1操作
//问：最少操作多少次能够将所有数字变成相同的
//最终变成相同的目标为中位数即可，如果中位数有两个x,y则区间[x,y]均可。
//2 1 0 1 2 3 -->总共9
//1 2 3 7 8 9
题目链接：https://www.luogu.com.cn/problem/P14918?contestId=334554
#include<bits/stdc++.h>
using namespace std;
int n,x,ans;
const int N=1e5+10;
vector<int> a[N];
int main(){
cin>>n;
//0//x
for(int i=0;i<n;i++){
cin>>x;
//优化，sqrt
for(int j=2;j*j<=x;j++){
int cnt=0;
if(x%j==0){
while(x%j==0){
x/=j;
cnt++;
}
a[j].push_back(cnt);
}
}
if(x>1){
a[x].push_back(1);
}
}
//2 3 5
//2 1 0 0
for(int i=0;i<N;i++){
sort(a[i].begin(),a[i].end());
int mid=n/2;//确定位置
int zero_cnt=n-a[i].size();//0的数量
if(mid<zero_cnt){
mid=0;
}else{
mid=mid-zero_cnt;
mid=a[i][mid];
}
ans+=zero_cnt*mid;//0本身产生的贡献
for(auto x:a[i]){
ans+=abs(x-mid);
}
}
cout<<ans;
return 0;
}
题目链接：https://www.luogu.com.cn/problem/T774737?contestId=334554
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int>PII;
typedef pair<PII,int>PPI;
const int N=1e5+5;
const int mod=1e6+7;
int din[N];
vector<int>vct;
void solve(){
int n,m;
cin>>n>>m;
map<int,int>mp;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
din[u]++;
din[v]++;
}
for(int i=1;i<=n;i++){
mp[din[i]]++;
}
for(auto v:mp){
vct.push_back(v.first);
// cout<<v.first<<"\n";
}
int sum=0;
for(int i=0;i<vct.size();i++){
for(int j=0;j<vct.size();j++){
sum+=(vct[i]^vct[j])*(vct[i]|vct[j])*(vct[i]&vct[j])*(mp[vct[i]]*mp[vct[j]]);
}
}
cout<<sum/2<<"\n";
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int _=1;
// cin>>_;
while(_--){
solve();
}
}
//5 6
//1 2
//1 3
//1 4
//2 5
//5 2
//3 4
//gcd 最大公因数
//辗转相除法 扩展欧几里得
//1/2%10
//同余方程
//a%c<=>b%c;
//直接函数 __gcd(a,b); log(min(a,b));
ll gcd(ll a,ll b){
if(b==0)return a;
return gcd(b,a%b);
}
//lcm 最小公倍数
//a*b=gcd*lcm;
//lcm=a*b/gcd;
//已知a求一个b
//要求r(a,b)/(a+b)
//a#b/(a+b) b=2a;
//a#b/a=1000002
//鸽巢定理
//n个鸽巢 n+1个鸽子
//最多的鸽巢，最少有几只鸽子 2
https://www.luogu.com.cn/problem/B3715?contestId=333384
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
void solve(){
ll n;cin>>n;
for(ll i=2;i*i<=n;i++){
while(n%i==0){
cout<<i<<' ';
n/=i;
}
}
if(n!=1)cout<<n;
cout<<endl;
}
int main(){
int t=1;
cin>>t;
while(t--){
solve();
}
}
https://www.luogu.com.cn/problem/P8754?contestId=333384#ide
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
void solve(){
ll n;cin>>n;
ll x=1;
for(ll i=2;ii<=n;i++){
int cnt=0;//统计数量
while(n%i==0){
cnt++;
n/=i;
}
if(cnt%2){
x=i;//补充一个
}
}
if(n!=1){
x*=n;
}
cout<<x<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
https://www.luogu.com.cn/problem/B4398?contestId=333384
//2 2
//8 2
//3 3
//18 2
//84 37
//拆解为奇数因子乘积的形式(且只保留一个即可)
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
//3e7 --->256MB
#define ll int
// pair<int,int>;
int a[N];
ll run(ll x){
ll res=1;//拆解结果
for(ll i=2;ii<=x;i++){
ll cnt=0;//统计数量
while(x%i==0){
x/=i;
cnt++;
}
if(cnt%2)res*=i;
}
return res*x;//得到最终的素数拆解(只保留奇数且单个素数)
}
void solve(){
// map<ll,ll>mp;//数组
//map<下标,值> 平衡树 //离散化--->
int n;cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
a[run(x)];
// mp[run(x)];
// cout<<x<<' '<<run(x)<<endl;
}
int mx=0;
for(int i=1;i<N;i++){
mx=max(mx,a[i]);
}
cout<<mx<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
https://www.luogu.com.cn/problem/P1414?contestId=333384#ide
//直接计算每个数的因子贡献
//30 1 2 3 5 6 10 15 30
//12 1 2 3 4 6 12
//25 1 5 25
//
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
int a[N];
map<int,int>mp;
//9 ;1 3 9
void run(int x){
for(int i=1;i*i<=x;i++){
if(x%i==0){
mp[i];//左边
if(x/i!=i){//特判中间
mp[x/i];//右边
}
}
}
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
run(x);
}
for(auto cur:mp){//便利所有拆解计数
a[cur.second]=max(a[cur.second],cur.first);//保留最大答案
}
for(int i=n;i>0;i--){
a[i]=max(a[i+1],a[i]);//后缀最大值
}
for(int i=1;i<=n;i++){
cout<<a[i]<<endl;;
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个