想吃冰卻又敏感保護不足?金豪禮★拿現金最實在!輕忽小中風,當心變殘障反服貿流血 法官要警交...
2012-10-13 11:29:56 人氣(66) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][數學] 10680 - LCM

0
收藏
0
推薦

Problem H
LCM

Input: standard input
Output:
standard output
Time Limit:
2 seconds

All of you know about LCM (Least Common Multiple). For example LCM of 4 and 6 is 12. LCM can also be defined for more than 2 integers. LCM of 2, 3, 5 is 30. In the same way we can define LCM of first N integers. The LCM of first 6 numbers is 60.

As you will see LCM will increase rapidly with N. So we are not interested in the exact value of the LCM but we want to know the last nonzero digit of that. And you have to find that effeciently.

Input

Each line contains one nonzero positive integer which is not greater than 1000000. Last line will contain zero indicating the end of input. This line should not be processed. You will need to process maximum 1000 lines of input.

Output

For each line of input, print in a line the last nonzero digit of LCM of first 1 to N integers. 

Sample Input                              Output for Sample Input

3
5
10

0

6
6

2


Problemsetter: Md. Kamruzzaman, Member of Elite Problemsetters’ Panel
Special thanks to: Mohammad Sajjad Hossain


求 1...N的最小公倍數的最後一位非零的數。
這一題假使我們知道 1...N 的最小公倍數就可以知道 1...N+1 的最小公倍數。
如果 N+1 是某一個質數p的次方時,則將 LCM(N)*p = LCM(N+1)。

計算時使用大數乘法會比較保險,不過要隨時將尾數0的去掉,保留幾位自行選擇,不然全部記錄很消耗時間。

#include <stdio.h>
#include <math.h>
char f[1000001];
int apart(int n) {
    int i, sq = (int)sqrt(n);
    int flag = 0;
    for(i = 2; i <= sq; i++) {
        if(n%i == 0) {
            while(n%i == 0)
                n /= i;
            flag = 1;
            break;
        }
    }
    if(flag && n == 1)
        return i;
    if(!flag)
        return n;
    return 0;
}
int bigNum[101] = {2}, tmp[101] = {};
int len = 1;
void mult(int n) {
    int i, j;
    for(i = 0; i <= len; i++)
        tmp[i] = bigNum[i]*n;
    for(i = len+1; i <= len+10; i++)
        tmp[i] = 0;
    for(i = 0; i <= len+10; i++) {
        tmp[i+1] += tmp[i]/10, tmp[i] %= 10;
    }
    j = 0;
    while(tmp[j] == 0)  j++;
    for(i = 0; i <= len+10; i++, j++)
        bigNum[i] = tmp[j];
    len += 10;
    while(!bigNum[len]) len--;
    if(len > 10)    len = 10;
}
int main() {
    f[1] = 1, f[2] = 2;
    int i, j;
    for(i = 3; i <= 1000000; i++) {
        j = apart(i);
        if(j)   mult(j);
        f[i] = bigNum[0];
    }
    while(scanf("%d", &i) == 1 && i)
        printf("%d\n", f[i]);
    return 0;
}

10680LCM
台長:Morris
人氣(66) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][dp][2DLIS] 1196 - Tiling Up Blocks
此分類上一篇:[UVA][建表] 974 - Kaprekar Numbers

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文