CF27.E. Number With The Given Amount Of Divisors

简介:

这题让求因子数为n的数中的最小的值。思路是先把n质因子分解成x1*x2*x3*x4...(注意x1,x2,x3,x4可能有相等情况)这种形式,然后把n的所有因子由大到小排序,然后可以还原成素数乘方的形式 ans=2^(x1-1)*3^(x2-1)*5^(x3-1)... 但是要注意的是这个答案可能是最终答案,但是有特例,比如8=2*2*2 根据上一个公式计算的ans=2^1*3^1*5^1=30 但是如果把8分成4*2 那么ans=2^3*3^1=24这样是最优解 因为2^1*5^1>2^3 所以先通过一个循环找出n的最优因子分解,可能不是质因子,再根据公式ans=2^(x1-1)*3^(x2-1)*5^(x3-1)...就是答案 最后注意精度问题就可以了 这题小题大做了 用了rho启发式质因子分解 也可以用素数表打出1000以内的素数来进行质因子分解

#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long int64;
int64 gcd(int64 a,int64 b)
{
    if (a==0) return 1;
    if(a<0) return gcd(-a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
int64 modmult(int64 a,int64 b,int64 n)//a*b%n
{
    a%=n;
    int64 ret;
    for(ret=0; b; a=(a<<1)%n,b>>=1)
        if(b&1)
            ret=(ret+a)%n;
    return ret;
}
int64 modular(int64 a,int64 b,int64 n)//renturn a^b%n
{
    int64 ans=1;
    a%=n;
    while(b)
    {
        if(b&1)
            ans=modmult(ans,a,n),b--;
        b>>=1;
        a=modmult(a,a,n);
    }
    return ans;
}
bool witness(int64 a,int64 n)//判断 a^(n-1)=1(mod n)
{
    int t=0;
    int64 x,xi,temp=n-1;
    while(temp%2==0)
        t++,temp/=2;
    xi=x=modular(a,temp,n);
    for(int i=1; i<=t; i++)
    {
        xi=modmult(xi,xi,n);
        if(xi==1&&x!=1&&x!=n-1)
            return 1;
        x=xi;
    }
    if(xi!=1)
        return 1;
    return 0;
}
bool millar_rabin(int64 n,int s)
{
    for(int j=1; j<=s; j++)
    {
        int64 a=rand()%(n-1)+1;//a=rand()%(Y-X+1)+X; /*n为X~Y之间的随机数
        if(witness(a,n))
            return 0;
    }
    return 1;
}
int64 pollard_rho(int64 n,int64 c)
{
    int64 i=1,k=2,x,y;
    x=rand()%n;
    y=x;
    while(1)
    {
        i++;
        x=(modmult(x,x,n)+c)%n;
        int64 d=gcd(y-x,n);
        if(d!=1&&d!=n)
            return d;
        if(x==y)
            return n;
        if(i==k)
        {
            y=x;
            k+=k;
        }
    }
}
int64 factor[100];
int tol;
void findfac(int64 n)
{
    if(millar_rabin(n,10))
    {
        factor[tol++]=n;
        return;
    }
    int64 p=n;
    while(p>=n)
        p=pollard_rho(p,rand()%(n-1)+1);
    findfac(p);
    findfac(n/p);
}
void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        d=a;
        return;
    }
    else
    {
        exgcd(b,a%b,d,x,y);
        long long temp=x;
        x=y;
        y=temp-(a/b)*y;
    }
}
int cmp(int64 a,int64 b)
{
    return a>b;
}
bool isprime[2000];
int nprime,prime[2000];
void getprime()
{
    long long i,j;
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    nprime=0;
    for(i=2; i<2000; i++)
    {
        if(isprime[i])
        {
            prime[++nprime]=i;
            for(j=i*i; j<2000; j+=i)
                isprime[j]=0;
        }
    }
}
int main()
{
    long long n;
    getprime();
    while(cin>>n)
    {
        if(n==1)
        {
            cout<<1<<endl;
            continue;
        }
        tol=0;
        findfac(n);
        sort(factor,factor+tol,cmp);
        long long ans=1;
        for(int i=0; i<tol; i++)
            for(int j=i+1; j<tol; j++)
            {
                if(pow(prime[i+1],factor[i]*factor[j]-1)<pow(prime[i+1],factor[i]-1)*pow(prime[j+1],factor[j]-1))
                {
                    factor[i]*=factor[j];
                    factor[j]=1;
                    for(int k=j; k<tol-1; k++)
                        swap(factor[k],factor[k+1]);
                }
            }
        for(int i=0; i<tol; i++)
            ans*=(int64)(pow(prime[i+1],factor[i]-1)+1e-14);
        cout<<ans<<endl;
    }
    return 0;
}


目录
相关文章
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
98 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
43 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
39 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
94 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
96 0
LeetCode 313. Super Ugly Number
|
算法
LeetCode 306. Additive Number
累加数是一个字符串,组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
122 0
LeetCode 306. Additive Number
|
算法
LeetCode 268. Missing Number
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
89 0
LeetCode 268. Missing Number
LeetCode 264. Ugly Number II
编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。
71 0
LeetCode 264. Ugly Number II