首页 > 其他 > 详细

hdu4002 Find the maximum 欧拉函数

时间:2015-05-29 18:10:16      阅读:205      评论:0      收藏:0      [点我收藏+]
//求小于N且n/phi(x)最大的n如果有多个,输出最小的
//phi(x) = x*(1-1/p1)*(1-1/p2)*(1-1/p3)....
//要使得x/phi(x) 最大,即使得(1-1/p1)*(1-1/p2)*(1-1/p3)....最小
//又p1, p2 , p3 , ....
//全为素数因子,所以可以对枚举所有素数因子乘积,
//打表后找小于等于n的数
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn  = 1010;
char str[maxn] ;
int num[maxn][maxn] ;
int num_1[maxn] ;
int len[maxn] ;
int isp[maxn] ;
int prime[maxn] ;
int set()
{
    memset(isp , 0  ,sizeof(isp)) ;
    isp[1] = 1;
    for(int i = 4;i < maxn;i+=2)
    isp[i] = 1;
    for(int i = 3;i < maxn;i++)
    {
        if(isp[i])continue ;
        for(int j = i*i;j < maxn;j+=i)
        isp[j] = 1;
    }
    int j = 0 ;
    for(int i = 1;i < maxn;i++)
    if(!isp[i])prime[++j] = i ;
    return j ;
}
bool cmp(int len_1 , int len_2 , int pos)
{
    if(len_1 > len_2)return 0 ;
    if(len_2 > len_1)return 1 ;
    for(int i = len_1 ;i > 0;i--)
    {
        if(num_1[i] > num[pos][i])
        return 0 ;
        if(num_1[i] < num[pos][i])
        return 1 ;
    }
    return 0 ;
}
void init()
{
    int sum = set() ;
    num[0][1] = 1;
    len[0] = 1;
    for(int i = 1;;i++)
    {
        int c = 0 ;
        len[i] = len[i-1] ;
        for(int j = 1;j <= len[i];j++)
        {
            num[i][j] = prime[i]*num[i-1][j] ;
            num[i][j] += c ;
            c = num[i][j]/10 ;
            num[i][j] %= 10 ;
        }
        while(c)
        {
            num[i][++len[i]] = c%10 ;
            c/=10 ;
        }
        if(len[i] > 100)break;
    }
}
int main()
{
    init() ;
    int T ;
    scanf("%d" , &T) ;
    while(T--)
    {
        scanf("%s" , str) ;
        int len_1 = strlen(str) ;
        for(int i = len_1 - 1;i >= 0 ;i--)
        num_1[len_1 - i] = str[i] - ‘0‘ ;
        int pos = 1;
        while(!cmp(len_1 , len[pos] , pos))pos++ ;
        for(int i = len[pos-1];i >= 1;i--)
        printf("%d" , num[pos-1][i]) ;
        puts("") ;
    }
}

hdu4002 Find the maximum 欧拉函数

原文:http://blog.csdn.net/cq_pf/article/details/46237849

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!