UC知道有关最小公倍数的问题
来源：百度知道 编辑：UC知道 时间：2024/05/31 03:27:38
Problem Description
Lemon wants to be a hero since he was a child. Recently he is reading a book called “Where Is Hero From” written by ZTY. After reading the book, Lemon sends a letter to ZTY. Soon he recieves a reply.
Dear Lemon,
It is my way of success. Please caculate the algorithm, and
secret is behind the answer. The algorithm follows:
Int Answer(Int n)
{
.......Count = 0;
.......For (I = 1; I <= n; I++)
.......{
..............If (LCM(I, n) < n * I)
....................Count++;
.......}
.......Return Count;
}
The LCM(m, n) is the lowest common multiple of m and n.
The data n = 1, 3, ..., ...
It is easy for you, isn’t it.
Please hurry up!
ZTY
What a good chance to be a hero. Lemon can not wait any longer. Please help Lemon get the answer as soon as possible.
Input
First line contains an integer T(1 <= T <= 1000000) indicates the number of te
Lemon wants to be a hero since he was a child. Recently he is reading a book called “Where Is Hero From” written by ZTY. After reading the book, Lemon sends a letter to ZTY. Soon he recieves a reply.
Dear Lemon,
It is my way of success. Please caculate the algorithm, and
secret is behind the answer. The algorithm follows:
Int Answer(Int n)
{
.......Count = 0;
.......For (I = 1; I <= n; I++)
.......{
..............If (LCM(I, n) < n * I)
....................Count++;
.......}
.......Return Count;
}
The LCM(m, n) is the lowest common multiple of m and n.
The data n = 1, 3, ..., ...
It is easy for you, isn’t it.
Please hurry up!
ZTY
What a good chance to be a hero. Lemon can not wait any longer. Please help Lemon get the answer as soon as possible.
Input
First line contains an integer T(1 <= T <= 1000000) indicates the number of te
提示一下吧：
lcm(l,n)<n*l<==>l*n/gcd(l,n)<n*l<==>gcd(l,n)>1
问题显然了，就是求totient...
其实这道题目出题的人只是稍稍转化了经典概念而已。
结合数论的知识就可以写出高效的代码。
int eular(int n){
int ret=1,i;
for (i=2;i*i<=n;i++)
if (n%i==0){
n/=i,ret*=i-1;
while (n%i==0)
n/=i,ret*=i;
}
if (n>1)
ret*=n-1;
return ret;
}
没太看明白，不过应该不是求最小公倍