当前位置:网站首页>C - Divisors of the Divisors of An Integer Gym - 102040C
C - Divisors of the Divisors of An Integer Gym - 102040C
2022-07-05 14:01:00 【beyond+myself】
Topic link
The question : Is o n! The number of factors in the factor
Answer key :
①:n! The number of a factor in is n/x Accumulation .
prove : In fact, it is one layer at a time , That is, each removal can be divided into 1 individual 3 Of , Two in turn 3 Of , Three 3 The number of , Finally, you can get 3 The number of , There's no need to
to be divisible by , Because it's a factorial , So even if it can't be divisible , It can also be divided by smaller numbers in the array .
Let's give you an example :
1234567 We find what we finally get 2 The number of , for the first time We found that 2 4 6 Divisibility , After division, it becomes 1 2 3 then 7/2=3,ans+=3, then 2 Still divisible , And then it became 1, then 3/2=1, You can't divide the rest , So we can find this rule .
②: Suppose we can turn the result of factorial into something similar to 2 ^ a * 3 ^ b * 5 ^ c In this way , We can get the result —— yes (a+1)*(a+2) / 2 * (b+1) * (b+2) / 2 *(c+1) * (c+2) / 2;
prove : After we write them in the above form , In fact, the factor is easy to find , If you let me find the number of factors , That's all for this question , But the question requires the number of factors , So we can't finish here , The number of factors is —— We just ask
A prime unit , For example :3 ^ 0 The number of factors of is 1 individual ,3 ^ 1 Are the two ,3 ^ a The number of factors ( 3 ^ 0 ~ 3 ^ a) common a+1 individual therefore We add them up to (a+1) * (a+2)/2 such Multiply all of them , That is, the number of cases similar to permutation and combination , When all numbers are selected 0 Inferior time , That is to say 1.
Here is AC Code :
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e6+10,mod=1e7+7;
int prime[N];
bool st[N];
int cnt[N];
int cou;
void is_prime(int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if(!st[i])
{
prime[cou++]=i;
for(j=i+i;j<=n;j+=i) st[j]=true;
}
}
}
signed main()
{
is_prime(1e6);
int n;
while(cin>>n&&n)
{
memset(cnt,0,sizeof(cnt));
for(int i=0;prime[i]<=n;i++)
{
cnt[i]=0;
int tmp=n;
while(tmp)
{
cnt[i]+=tmp/prime[i];
tmp/=prime[i];
}
}
int ans=1;
for(int i=0;prime[i]<=n;i++)
{
if(cnt[i]>0)
{
ans=(ans%mod*((cnt[i]+1)*(cnt[i]+2)/2)%mod)%mod;
}
}
printf("%lld\n",ans);
}
return 0;
}
边栏推荐
猜你喜欢
Liar report query collection network PHP source code
Financial one account Hong Kong listed: market value of 6.3 billion HK $Ye wangchun said to be Keeping true and true, long - term work
What category does the Internet of things application technology major belong to
::ffff:192.168.31.101 是一个什么地址?
NFT value and white paper acquisition
牛客网:拦截导弹
Recommendation number | what are interesting people looking at?
研究生可以不用学英语?只要考研英语或六级分数高!
IP packet header analysis and static routing
Detailed explanation of IP address and preparation of DOS basic commands and batch processing
随机推荐
Kotlin collaboration uses coroutinecontext to implement the retry logic after a network request fails
leetcode 10. Regular expression matching regular expression matching (difficult)
Controller in laravel framework
Wechat app payment callback processing method PHP logging method, notes. 2020/5/26
深拷贝真难
Can graduate students not learn English? As long as the score of postgraduate entrance examination English or CET-6 is high!
LeetCode_3(无重复字符的最长子串)
Laravel generate entity
登录界面代码
瑞能实业IPO被终止:年营收4.47亿 曾拟募资3.76亿
WebRTC的学习(二)
2022 machine fitter (Advanced) test question simulation test question bank simulation test platform operation
Leetcode array question brushing notes
故障分析 | MySQL 耗尽主机内存一例分析
判断变量是否为数组
Zhubo Huangyu: it's really bad not to understand these gold frying skills
[South China University of technology] information sharing of postgraduate entrance examination and re examination
Zhubo Huangyu: these spot gold investment skills are not really bad
2022 construction welder (special type of construction work) special operation certificate examination question bank and online simulation examination
Internal JSON-RPC error. {"code":-32000, "message": "execution reverted"} solve the error