HDU 4196 Remoteland (数论 n!相关)

迷南。 2022-09-19 12:16 139阅读 0赞

题意：用不大于n的所有正数去组成一个尽可能大的完全平方数。

思路：显然取n!是最大的，设其为a，但这不一定是一个完全平方数，需要把多余的部分除掉。

可以利用勒让德定理很快处理出n!所有素因子的指数，偶数保留，奇数-1，即可保证这些素因子最后乘积为完全平方数，也就是用a除以所有指数为奇数的素因子的乘积。注意由于有取模运算，所以不能直接除。

#include <cstdio>
    #include <cstring>
    
    const int mod=1000000007;
    
    const int N=10000005;
    int prime[670000],np=0;
    __int64 fac[N];
    bool tag[N];
    
    void Init ()
    {
    	int i,j;
        for (i=2;i<N;i++) if (tag[i] == false)
        {
            prime[np++]=i;
            for (j=i+i;j<N;j+=i)
                tag[j]=true;
        }
    	fac[1]=1;
    	for (i=2;i<N;i++)
    		fac[i]=fac[i-1]*i%mod;
    }
    
    __int64 POW (__int64 s,__int64 index,__int64 mod)
    {
        __int64 ans=1;
        s%=mod;
        while (index>=1)
        {
            if ((index&1)==1)   //奇数
                ans=(ans*s)%mod;
            index>>=1;
            s=s*s%mod;
        }
        return ans;
    }
    
    int Cal (int n,int p)
    {
    	int sum=0;
    	while (n)
    		sum+=(n/=p);
    	return sum;
    }
    
    int main ()
    {
        int n;
    	Init ();
        while (scanf("%d",&n),n)
        {
    		__int64 ans=1;
    		for (int i=0;i<np && prime[i]<=n;i++)
    		{
    			int tmp=Cal(n,prime[i]);
    			if (tmp&1)   //奇数
    				ans=(ans*prime[i])%mod;
    		}
    		ans=fac[n]*POW(ans,mod-2,mod)%mod;
    		printf("%I64d\n",ans);
        }
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 5584- LCM Walk 【数论】

题意：给你一个x和y，z = lcm(x, y)，每次x加上z或者y加上z，然后给你一个终点，问你最多能从几个点转移过来的。思路：对于给定的终点(x, y) , 我们可以知

你的名字/ 2023年08月17日 17:29/ 0 赞/ 108 阅读

相关 HDU 4196 Remoteland (数论 n!相关)

题意：用不大于n的所有正数去组成一个尽可能大的完全平方数。思路：显然取n!是最大的，设其为a，但这不一定是一个完全平方数，需要把多余的部分除掉。可以利用勒让德定理很快处

迷南。/ 2022年09月19日 12:16/ 0 赞/ 140 阅读

相关数论 Lucas定理 hdu3037

对于C(n, m) mod p。这里的n，m，p（p为素数）都很大的情况。就不能再用C(n, m) = C(n - 1，m) + C(n - 1, m - 1)的公式递推了。

àì夳堔傛蜴生んèń/ 2022年08月18日 01:58/ 0 赞/ 195 阅读

相关 HDU 5495 LCS（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5495 参考博客： http://blog.csdn.net/queue

小咪咪/ 2022年08月09日 01:59/ 0 赞/ 158 阅读

相关 N！Again（数论）

N！Again Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/O

落日映苍穹つ/ 2022年08月07日 15:58/ 0 赞/ 91 阅读

相关 HDU 5750 Dertouzos（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5750 题目大意：x能整除n，x就是n的positive proper div

谁借莪１个温暖的怀抱￠/ 2022年07月20日 12:15/ 0 赞/ 130 阅读

相关 HDU 5755 Gambler Bo（数论）

题目链接： http://acm.split.hdu.edu.cn/showproblem.php?pid=5755 题目大意：给你一个矩阵，矩阵中是0，1，2三个

素颜马尾好姑娘i/ 2022年07月16日 23:27/ 0 赞/ 171 阅读

相关 HDU 5768 Lucky7（数论）

题目链接： http://acm.split.hdu.edu.cn/showproblem.php?pid=5768 题目大意：求出一个区间内模7余0，但是模一些给定的互

电玩女神/ 2022年07月16日 23:26/ 0 赞/ 182 阅读

相关 HDU 3988(数论)

问题描述: iSea is tired of writing the story of Harry Potter, so, lucky you, solving the fo

浅浅的花香味﹌/ 2022年05月31日 05:06/ 0 赞/ 180 阅读

相关数论之整数相关

近期计划学习区块链，鉴于底层原理基础，主要从两个方向学起，一方面学习区块链相关原理及技术，另一方面从底层支撑开始，学习密码学等底层知识，其中数论作为密码学基础，因此从初等数论着

- 日理万妓/ 2022年05月25日 04:40/ 0 赞/ 118 阅读