首页 > 其他分享 >Asia Dhaka Regional Contest C (阶乘分解)

Asia Dhaka Regional Contest C (阶乘分解)

时间:2023-05-05 14:33:06浏览次数:41  
标签:Dhaka Contest 个数 times 因子 阶乘 include define

原题点这

前置知识点:

题意:

给出 \(n\),问 \(n!\) 的因子的因子的个数和。

思路:

学会上面的阶乘分解之后,我们能一眼看出来这道题也一定跟它有关系,所以我们按照惯例先对\(n!\) 进行质因数分解。

n! = \({p_1}^{a_1}\times\) \({p_2}^{a_2}\)\(\times\) \({p_3}^{a_3}\)\(\times\) ... \(\times\) \({p_k}^{a_k}\)

我们单独考虑每一中质数,我们假设一个素数为 \(p\),它的幂次为 \(a\) ,因为我们要求的是因子的因子个数,而且它一共有幂次 \(a\) ,那么该因子的因子就有 \(0,1,2 ...a\) 的 \(a + 1\) 种选择。
即\(p^{0},p^{1},p^{2},,,,p^{a}\)
对于\(p^0\),因子个数为1,对于\(p^1\),因子个数为2,对于\(p^a\),因子个数为\(a+1\)。所以总的因子个数就为:\(1+2+3+...+a+(a+1) = \dfrac{(a+1)(a+2)}{2}\) (等差数列求和)

而对于每一个素数的贡献都如上,所以总贡献为:\(\prod_{i=1}^{k}\dfrac{(a_i+1)(a_i+2)}{2}\)。

AC代码:

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define xx first
#define yy second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define fixed fixed<<setprecision
#define endl '\n'
#define int long long

using namespace std;

const int mod = 1e7 + 7;
const int N2 = 1e6 + 10;

int cntt, primes[N2], n;
bool stt[N2];
// 线性筛质数
void initpr(int n)
{ 
    for(int i = 2; i <= n; i ++)
    { 
        if(!stt[i]) primes[cntt ++] = i;
        for(int j = 0; primes[j] * i <= n; j ++)
        {
            stt[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    } 
}
// 阶乘分解
int f(int x)
{
    int res = 0, tt = n;
    while(tt)
    {
        res += tt / x;
        tt /= x;
    }
    return res;
}

void solve()
{
    while(cin >> n && n)
    {
        int res = 1;
        for(int i = 0; i < cntt && primes[i] <= n; i ++)
        {
            int num = f(primes[i]);
            res = (res * (num + 1) * (num + 2) / 2) % mod;
        }
        cout << res << endl;
    }
}

signed main()
{
    IOS
    initpr(N2);
    int T = 1;
    //cin >> T;
    while(T --)
    {
        solve();
    }
    
    return 0;
}

标签:Dhaka,Contest,个数,times,因子,阶乘,include,define
From: https://www.cnblogs.com/liqs2526/p/17374077.html

相关文章

  • SMU Spring 2023 Trial Contest Round 10
    A.RemoveDuplicates#include<bits/stdc++.h>//#defineinf0x3f3f3f3f#defineendl'\n'#defineintlonglongusingnamespacestd;constintN=2e3+10,mod=1e9+7;//typedeflonglongll;typedefpair<int,int>PII;//queue......
  • The 2022 ICPC Asia Hangzhou Regional Programming Contest--M题 (字典树)
    https://codeforces.com/gym/104090/problem/K题意:给你n个字符串,在给你m个字符大小顺序规则。求逆序对数量。1.常规求这n个字符串的逆序对数量O(n^2)的时间复杂度,必爆,肯定要想办法优化,就往预处理上想。2.在不同规则下,比较这n个字符串谁大,两个字符串比较谁大,无论什么字符串大,......
  • AtCoder Regular Contest 128 E K Different Values
    洛谷传送门AtCoder传送门考虑判断有无解。把序列分成\(c=\left\lceil\frac{len}{k}\right\rceil\)段,则\(\foralla_i\lec\)且\(\sum\limits_{i=1}^n[a_i=c]\le((len-1)\bmodk)+1\)。必要性显然。充分性可以考虑直接构造,不难证明。考虑如何构造字典序最小......
  • AtCoder Regular Contest 134 D Concatenate Subsequences
    洛谷传送门AtCoder传送门我一年前甚至不会做/qd发现\(a_{x_1}\)为\(k=\min\limits_{i=1}^na_i\)时最优。然后开始分类讨论:如果\(\min\limits_{a_i=k}a_{i+n}\lek\),答案为\((k,\min\limits_{a_i=k}a_{i+n})\)。这是因为如果再选一个\(k\)肯定不优。否则......
  • AtCoder Beginner Contest 300
    A-N-choicequestion#include<bits/stdc++.h>usingnamespacestd;intread(){intx=0,f=1,ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-......
  • AtCoder Regular Contest 128 D Neq Neq
    洛谷传送门AtCoder传送门考虑把所有\(a_i=a_{i+1}\)的位置断开,分别计算然后把方案数乘起来。接下来的讨论假设\(a_i\nea_{i+1}\)。考虑一个dp,设\(f_i\)为\([1,i]\)最后剩下的集合的方案数。转移显然是\(f_i\getsf_i+f_j\),但是需要满足\((a_j,a_{j+1},...,......
  • AtCoder Beginner Contest 242(D,E)
    AtCoderBeginnerContest242(D,E)D(二叉树搜索)D题目大意就是首先给你一个字符串,代表\(S^0\),然后我们可以操作得到\(S^1,S^2\)等等我们可以知道\(S^i\)是拿\(S^(i-1)\)经过一系列替换而来的,因为这个字符串只有三种字符串,\(A,B,C\),这个替换方式就是把\(A\)替换成\(BC\),把\(B\)......
  • AtCoder Regular Contest 125 F Tree Degree Subset Sum
    洛谷传送门AtCoder传送门首先将度数\(-1\)。设\(f_i\)为体积为\(i\)至多能用几个物品凑出来,\(g_i\)为至少。我们现在要证明一个东西:\(x\in[g_i,f_i]\),\((i,x)\)合法。首先若\((s,x)\)合法,那么必须满足\(s-x\in[-z,z-2]\),其中\(z=\sum\limits_{i=1}......
  • AtCoder Regular Contest 119 F AtCoder Express 3
    洛谷传送门AtCoder传送门很厉害的题!考虑所有车站已确定,如何求\(0\)到\(n+1\)的最短路。设\(g_{i,0}\)为只考虑\(0\simi\)的点,到\(i\)和它左边第一个\(\text{A}\)的最短路,\(g_{i,1}\)同理。有转移:若\(s_{i-1}=\text{A},s_i=\text{A},g_{i,0}\getsg_{......
  • AtCoder Regular Contest 119 D Grid Repainting 3
    洛谷传送门AtCoder传送门对每个红格的行和列连边,建出二分图。对于二分图中的每个连通块分别考虑。大胆猜测对于每个连通块,我们都能够进行适当的操作,使得只有一行/一列没被操作(显然不能使所有行和列都被操作)。对应的方案就是随便取一棵生成树,把不被染白的那一行/列拎出来当根,然......