[UVA] 12027 - Very Big Perfect Squares＠Morris' Blog

2012-06-30 20:49:43| 人氣1,098| 回應0 | 上一篇 | 下一篇

[UVA] 12027 - Very Big Perfect Squares

Background

An integer, n, is called a perfect square if there is another integer, m, such that n = m x m. Examples of perfect squares are 1, 4, 9, 16, 25, 36, etc. That is: 1, 2², 3², 4², 5², 6², etc.

Given a natural number, A, we want to know how many perfect squares exist between 1 and A, inclusive. For example, between 1 and 1 there is only one perfect square (1), between 1 and 5 there are 2 (1 and 4), between 1 and 40 there are 6 (1, 4, 9, 16, 25 and 36).

We want to work with very big numbers, so we are not very interested in accuracy. We only need the first digit of the result, and the rest of digits can be 0.

Input

The input can contain different test cases.

For each test case, there is a line with a natural number A.

You can assume that A is between 1 y 10¹⁰⁰⁰, inclusive.

The output ends with a line with the value: 0.

Output

For each test case, the output should be a line with a natural number N, indicating how many perfect squares exist between 1 and A, inclusive.

As we do not need too much precision, you only have to output the most significant digit of the result. You have to complete the rest of the result with zeros. For example, if the result is 59, then you have to output 50; if the result is 12345, then you have to output: 10000.

Sample Input

Sample Output

這題只要表示成科學符號表式法, 大概就解一半了,
1. 長度是偶數 4000 => 6 * 10 (40開根號)
2. 長度是奇數 400 => 2 * 10 (4開根號)



#include <stdio.h>
#include <string.h>
#include <math.h>

int main() {
    char str[1005];
    while(scanf("%s", &str) == 1) {
        if(!strcmp(str, "0"))
            break;
        int len = strlen(str);
        int num = str[0]-'0', i;
        if(len > 1 && len%2 == 0) num = num*10 + str[1]-'0';
        len = (len-1)/2;
        printf("%d", (int)sqrt(num));
        for(i = 0; i < len; i++)
            putchar('0');
        puts("");
    }
    return 0;
}