2026年7月2日 - 数论 - 课堂笔
2026-07-02 11:41:48
发布于：广东
9阅读
0回复
0点赞
//二分
//二进制 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;
#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
#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;
}
#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
这里空空如也
有帮助，赞一个