2011年大連ACMネット試合hdu 4002 Find the maximum
7757 ワード
Find the maximum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 276 Accepted Submission(s): 141
Problem Description
Euler's Totient function, φ (n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n . For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
HG is the master of X Y. One day HG wants to teachers XY something about Euler's Totient function by a mathematic game. That is HG gives a positive integer N and XY tells his master the value of 2<=n<=N for which φ(n) is a maximum. Soon HG finds that this seems a little easy for XY who is a primer of Lupus, because XY gives the right answer very fast by a small program. So HG makes some changes. For this time XY will tells him the value of 2<=n<=N for which n/φ(n) is a maximum. This time XY meets some difficult because he has no enough knowledge to solve this problem. Now he needs your help.
Input
There are T test cases (1<=T<=50000). For each test case, standard input contains a line with 2 ≤ n ≤ 10^100.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
Statistic | Submit | Discuss | Note
题意：
寻找 1-n中 n/φ (n) 的最大值 其中 φ (n)为欧拉函数
気づいた
1 1
2-5 2=1*2
6-29 6=1*2*3
30-209 30=1*2*3*5
210-2309 210=1*2*3*5*7
.....
もとは1つの質量の乗算です
そしてjavaで時計を打った!
今ネットで証明書を探しましたが、いいですね.の歩行者の学習に供する
証明リンク:blog.csdn.net/tanhaiyuan/article/details/6747408
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 276 Accepted Submission(s): 141
Problem Description
Euler's Totient function, φ (n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n . For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
HG is the master of X Y. One day HG wants to teachers XY something about Euler's Totient function by a mathematic game. That is HG gives a positive integer N and XY tells his master the value of 2<=n<=N for which φ(n) is a maximum. Soon HG finds that this seems a little easy for XY who is a primer of Lupus, because XY gives the right answer very fast by a small program. So HG makes some changes. For this time XY will tells him the value of 2<=n<=N for which n/φ(n) is a maximum. This time XY meets some difficult because he has no enough knowledge to solve this problem. Now he needs your help.
Input
There are T test cases (1<=T<=50000). For each test case, standard input contains a line with 2 ≤ n ≤ 10^100.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
2 10 100
Sample Output
6 30HintIf the maximum is achieved more than once, we might pick the smallest such n.
Source
The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest
Recommend
lcy
寻找 1-n中 n/φ (n) 的最大值 其中 φ (n)为欧拉函数
分析：
我遇到这个题首先看到数据量10^100,就觉得这题可能有规律，于是写了一个c++程序打了一个表看了一下
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define inf (1<<30)
__int64 a[1001001];
void all()
{
__int64 i,j;
for(i=1;i<=1001000;i++)
a[i]=i;
for(i=2;i<=1001000;i++)
{
if(a[i]==i)
{
for(j=1;j*i<=1001000;j++)
a[i*j]=a[i*j]/i*(i-1);
}
}
}
ofstream fout("c:\ii.out");
int main()
{
double M=0;
int i,j,k;
int n,ans;
all();
for(j=1;j<100;j++)
{
n=j;
ans=0;
M=0;
for(i=0;i<=n;i++)
{
if(M 気づいた
1 1
2-5 2=1*2
6-29 6=1*2*3
30-209 30=1*2*3*5
210-2309 210=1*2*3*5*7
.....
もとは1つの質量の乗算です
そしてjavaで時計を打った!
今ネットで証明書を探しましたが、いいですね.の歩行者の学習に供する
証明リンク:blog.csdn.net/tanhaiyuan/article/details/6747408
import java.math.BigInteger;
import java.util.Scanner;
public class Main
{
static int pcount=0;
static int get[]= new int[1000];
public static void getprime()
{
boolean sum[]= new boolean[1000001];
int i,j;
for(i=2; i<100000; i++)
{
if(i%2==1)sum[i]=true;
}
int temp=(int)Math.sqrt(100000);
for(i=3; i0)
{
t--;
n=s.nextBigInteger();
if(n.compareTo(b6)<0)
{
if(n.compareTo(BigInteger.ONE)==0)
{
System.out.println("1");
}
else System.out.println("2");
}
else
for(i=1; i<102; i++)
{
if(n.compareTo(val[i])<=0)
{
System.out.println(val[i-1]);
break;
}
}
}
}
}