当前位置:网站首页>(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;
}
边栏推荐
- QT implementation fillet window
- Share an example of running dash application in raspberry pie.
- Click QT button to switch qlineedit focus (including code)
- Classic application of stack -- bracket matching problem
- 力扣:第81场双周赛
- (POJ - 3579) median (two points)
- Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
- 图图的学习笔记-进程
- 1005. Maximized array sum after K negations
- MariaDB的安装与配置
猜你喜欢
随机推荐
Browser print margin, default / borderless, full 1 page A4
1013. Divide the array into three parts equal to and
图图的学习笔记-进程
QT simulates mouse events and realizes clicking, double clicking, moving and dragging
Configuration du cadre flask loguru log Library
Suffix expression (greed + thinking)
1855. Maximum distance of subscript alignment
Data storage in memory & loading into memory to make the program run
第 300 场周赛 - 力扣(LeetCode)
Generate random password / verification code
Opencv learning log 27 -- chip positioning
(POJ - 3685) matrix (two sets and two parts)
Socket communication
Study notes of Tutu - process
Calculate the time difference
Problem - 1646C. Factorials and Powers of Two - Codeforces
AcWing:第56场周赛
Alice and Bob (2021 Niuke summer multi school training camp 1)
860. Lemonade change
409. Longest palindrome