[UVA][大數] 10433 - Automorphic Numbers
The Problem
Recreational mathematics is mathematics that is fun and used as either as a diversion from serious mathematics or as a way of making serious mathematics understandable or palatable. These are the pedagogic uses of recreational mathematics. They are already present in the oldest known mathematics and continue to the present day. One of the topic of the recreational mathematics is the Automorphic numbers which have many use in different fields.
Automorphic numbers are those numbers whose square ends with the number itself:
| 52 | = | 25, |
| 252 | = | 625, |
| 762 | = | 5776. |
The first automorphic numbers are 1, 5, 6, 25, 76, ... By definition 0 is not an Automorphic Number and for this particular problem we will not consider 1 as an Automorphic Number.
Automorphic numbers have enormous application in mathematics. In this problem you are to determine whether a given number is Automorphic or not.
The Input
Each line containing a arbitrarily big integer. Some Automorphic number have leading zeros. So leading zeros must be considered as significant. Input is terminated by end of file.The Output
If the input is an Automorphic number print ``Automorphic number of n-digit.'', where n is the number of digit of the integer which will not be greater then 2000. Otherwise print ``Not an Automorphic number.''.Sample Input
5 76 34
Sample Output
Automorphic number of 1-digit. Automorphic number of 2-digit. Not an Automorphic number.
Suman Mahbub
Created: 01-09-2002
Updated: 14-12-2002
做法：
這題有幾個要點要處理，特別是 0 與 1 不算是 Automaorphic Numbers
同時， 0001, 000001 .... 也都不是，就因為這樣錯了好多次。
有很多加速的地方，就如只有一些特別的尾數是可行解，特別判斷一下，
就可以在運算上比較好處理。
#include <stdio.h>
#include <string.h>
char in[5000];
int main() {
int i, j, k;
while(scanf("%s", in) == 1) {
if(!strcmp(in, "0") || !strcmp(in, "1")) {
puts("Not an Automorphic number.");
continue;
}
int x[3005] = {}, y[3005] = {};
int len = strlen(in);
for(i = 0, j = len-1; i < len; i++, j--)
x[j] = in[i]-'0';
int top = len-1;
while(top >= 0 && x[top] == 0)
top--;
if(top < 0 || (top == 0 && x[top] == 1)) {
puts("Not an Automorphic number.");
continue;
}
int error = 0;
for(i = 0; i < len && !error; i++) {
if(x[i])
for(j = 0; i+j < len; j++)
y[i+j] += x[i]*x[j];
y[i+1] += y[i]/10;
y[i] %= 10;
if(y[i] != x[i])
error = 1;
}
if(error)
puts("Not an Automorphic number.");
else
printf("Automorphic number of %d-digit.\n", len);
}
return 0;
}