当前位置:网站首页>[number theory] divisor
[number theory] divisor
2022-07-06 11:04:00 【Nathan Qian】
Try division to find the divisor
subject
explain
- Because divisors appear in pairs , So you just need to i*i<=x
- prevent x It's a total square , One more number is recorded . Therefore, special deposit is required x/i Conditions
Code segment
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>get_divisors(int x)
{
vector<int>ans;
for(int i=1;i*i<=x;i++)
{
if(x%i==0)
{
ans.push_back(i);
if(i!=x/i)ans.push_back(x/i);
}
}
sort(ans.begin(),ans.end());
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int x;cin>>x;
vector<int>ans=get_divisors(x);
for(auto x:ans)cout<<x<<' ';
cout<<endl;
}
return 0;
}
Find the number of divisors
subject
explain
- According to the above theorem , We should factorize each number , Then find the sum of prime factors
- be aware 1 Although it is a divisor , But the combination result is only 1 Kind of , So it's not in the scope
- about ans The multiplication modulus of cannot be written as ans*=x%mod, It can only be written as ans=ans*x%mod
Code segment
#include<iostream>
#include<unordered_map>
const int mod=1e9+7;
using namespace std;
unordered_map<int,int>primes;
int main()
{
int n;cin>>n;
while(n--)
{
int x;cin>>x;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
while(x%i==0)
{
primes[i]++;
x/=i;
}
}
}
if(x>1)primes[x]++;
}
long long ans=1;
for(auto it=primes.begin();it!=primes.end();it++)
{
ans=ans*(1+it->second)%mod;
}
cout<<ans%mod<<endl;
}
The sum of the approximations
subject
explain
- Here, please a1^α1 Sum of divisors of , It is obvious that there can be algebraic theorems
- Multiplication principle , It can be understood as the sum of each power combination of each prime number
- Select a number in each bracket and multiply it to exactly equal one of the divisors
- This does not repeat the choice of accumulation , That is, the sum of approximations
- When finding the sum of divisors of prime numbers , For the accumulation of proportional series
- The simple formula is
int t( frequency ) ,x( base number ),sum( and )
while(t--)
{
sum=sum*x+1;
}
Code segment
#include<iostream>
#include<unordered_map>
const int mod=1e9+7;
using namespace std;
int main()
{
int t;cin>>t;
unordered_map<int,int>primes;
while(t--)
{
int x;cin>>x;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
while(x%i==0)
{
primes[i]++;
x/=i;
}
}
}
if(x>1)primes[x]++;
}
long long sum=1;
for(auto it=primes.begin();it !=primes.end();it++)
{
long long tmp=1;
int t=it->second;
while(t--)
{
tmp=(tmp*it->first+1)%mod;
}
sum=sum*tmp%mod;
// Although it can guarantee tmp No more than mod, But if sum*tmp It is likely to be greater than mod
}
cout<<sum<<endl;
}
greatest common divisor
subject
explain
- Mathematical proof of Euclidean algorithm
- 【 number theory 】 Euclid algorithm _nathanqian123 The blog of -CSDN Blog
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int t;cin>>t;
while(t--)
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
}
}
边栏推荐
- 01项目需求分析 (点餐系统)
- CSDN问答标签技能树(五) —— 云原生技能树
- Ansible实战系列二 _ Playbook入门
- FRP intranet penetration
- Valentine's Day is coming, are you still worried about eating dog food? Teach you to make a confession wall hand in hand. Express your love to the person you want
- [leectode 2022.2.13] maximum number of "balloons"
- JDBC原理
- Data dictionary in C #
- February 13, 2022-3-middle order traversal of binary tree
- Mysql21 user and permission management
猜你喜欢
Mysql23 storage engine
Install mysql5.5 and mysql8.0 under windows at the same time
Postman Interface Association
A brief introduction to the microservice technology stack, the introduction and use of Eureka and ribbon
Csdn-nlp: difficulty level classification of blog posts based on skill tree and weak supervised learning (I)
CSDN blog summary (I) -- a simple first edition implementation
MySQL23-存儲引擎
MySQL master-slave replication, read-write separation
Mysql21 - gestion des utilisateurs et des droits
图像识别问题 — pytesseract.TesseractNotFoundError: tesseract is not installed or it‘s not in your path
随机推荐
MySQL21-用户与权限管理
CSDN问答标签技能树(一) —— 基本框架的构建
CSDN question and answer tag skill tree (I) -- Construction of basic framework
[recommended by bloggers] background management system of SSM framework (with source code)
Win10: how to modify the priority of dual network cards?
@controller,@service,@repository,@component区别
Copy constructor template and copy assignment operator template
Why is MySQL still slow to query when indexing is used?
打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
CSDN问答模块标题推荐任务(一) —— 基本框架的搭建
连接MySQL数据库出现错误:2059 - authentication plugin ‘caching_sha2_password‘的解决方法
JDBC原理
虚拟机Ping通主机,主机Ping不通虚拟机
JDBC原理
数数字游戏
Leetcode 461 Hamming distance
CSDN question and answer module Title Recommendation task (I) -- Construction of basic framework
[Thesis Writing] how to write function description of jsp online examination system
csdn-Markdown编辑器
Ansible practical Series III_ Task common commands