当前位置:网站首页>(lightoj - 1236) pairs forming LCM (prime unique decomposition theorem)
(lightoj - 1236) pairs forming LCM (prime unique decomposition theorem)
2022-07-06 16:23:00 【AC__ dream】
Topic link :Pairs Forming LCM - LightOJ 1236 - Virtual Judge
Chinese question meaning : Given a n Please lcm(a,b) Number to number ,lcm Represents the least common multiple , And (a,b) and (b,a) Treat as the same number pair .
analysis : set up n=p1^n1+p2^n2+……+pm^nm(m It's a subscript )
be a and b They can be expressed as
a=p1^a1+p2^a2+……+pm^am
b=p1^b1+p2^b2+……+bm^bm
Easy to know , if n=lcm(a,b), Then there are max(ai,bi)=ni, That is to say for n A qualitative factor of p,a and b contains p The maximum value of the power of the factor is equal to n contains p The power of the factor , That's for everyone pi factor ,ai and bi One of them must be ni, The other is 0~ni Any number in , So there is 2*(ni+1)-1=2*ni+1( Because both are ni It's a kind of emptying ), But contentment a<=b The number of cases except a=b=n This is not the case , Everything else is satisfaction a<b The number of cases is equal to a>b The number of cases , In addition to (n,n) Numbers other than this pair are divided by 2 that will do , That is to say (cal(n)-1)/2+1, Then add (n,n) In this case .
Here is the code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e7+9;
bool vis[N];
int prime[N],cnt;
void init()
{
for(int i=2;i<N;i++)
{
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<N;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
ll cal(ll n)
{
ll ans=1;
for(int i=1;i<=cnt&&prime[i]*prime[i]<=n;i++)
{
ll count=0;
while(n%prime[i]==0)
{
n/=prime[i];
count++;
}
ans*=(2*count+1);
}
if(n>1) ans*=(2*1+1);// also n This is the prime factor
return ans;
}
int main()
{
init();
int T;
cin>>T;
for(int _=1;_<=T;_++)
{
ll n;
scanf("%lld",&n);
printf("Case %d: %lld\n",_,cal(n)/2+1);
}
return 0;
}
边栏推荐
- Advancedinstaller安装包自定义操作打开文件
- Li Kou: the 81st biweekly match
- Classic application of stack -- bracket matching problem
- Write web games in C language
- 300th weekly match - leetcode
- QWidget代码设置样式表探讨
- QT有关QCobobox控件的样式设置(圆角、下拉框,向上展开、可编辑、内部布局等)
- Flag framework configures loguru logstore
- QT realizes window topping, topping state switching, and multi window topping priority relationship
- (POJ - 3685) matrix (two sets and two parts)
猜你喜欢
浏览器打印边距,默认/无边距,占满1页A4
1605. Sum the feasible matrix for a given row and column
2078. Two houses with different colors and the farthest distance
Read and save zarr files
Local visualization tools are connected to redis of Alibaba cloud CentOS server
1013. Divide the array into three parts equal to and
Some problems encountered in installing pytorch in windows11 CONDA
Share an example of running dash application in raspberry pie.
Vs2019 initial use
Click QT button to switch qlineedit focus (including code)
随机推荐
It is forbidden to trigger onchange in antd upload beforeupload
Share an example of running dash application in raspberry pie.
Educational Codeforces Round 130 (Rated for Div. 2)A~C
window11 conda安装pytorch过程中遇到的一些问题
Truck History
图图的学习笔记-进程
2027. Minimum number of operations to convert strings
Anaconda下安装Jupyter notebook
Problem - 1646C. Factorials and Powers of Two - Codeforces
1005. Maximized array sum after K negations
Understand what is a programming language in a popular way
antd upload beforeUpload中禁止触发onchange
Suffix expression (greed + thinking)
Opencv learning log 27 -- chip positioning
Ball Dropping
Analysis of protobuf format of real-time barrage and historical barrage at station B
Codeforces Round #801 (Div. 2)A~C
Codeforces Round #800 (Div. 2)AC
AcWing:第58场周赛
Opencv learning log 29 -- gamma correction