AOJ 760.尾数相等的数

142


题目



Description  


从键盘输入一个自然数K(1 < K < 99999999),一定存在自然数M和N(M < N),使得K的M次方和K的N次方均大于或等于1000,且它们的未尾三位数相等,则称M和N是一对“K尾相等数”。请编程序,输出K尾相等数中M+N最小值。



Input  


每一行包含一组测试数据,每组测试数据包含一个位长小于10的正整数K.



Output  


对每组测试数据输出一行。每行包含2个正整数M和N,两数之间用一个空格分隔。



Sample Input  


20
125



Sample Output  


3 4
2 4


题解



模拟操作即可,关键在于由于数据较大,而我们需要的只有后三位,因此不断%1000即可



注意1次方就符合条件的情况,和小于1000的情况



代码



/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;
 
//DEBUG MODE
#define debug 0
 
//循环
#define REP(n) for(int o=0;o<n;o++)
 
//初始化
#define mst(a) memset(a,-1,sizeof(a))
 
const int maxn = 1005;
int visited[maxn];
 
bool Do() {
    long long n;
    if(scanf("%lld",&n) == EOF)
        return false;
 
    mst(visited);
 
    int N,M,e = 1;
    long long k = n;
    while(k < 1000) {
        k *= n;
        e++;
    }
    k %= 1000;
    for(int i = 0;;i++) {
        if(visited[k] != -1) {
            N = e + i;
            M = visited[k];
            break;
        } else {
            visited[k] = e + i;
        }
        k *= n;
        k %= 1000;
    }
 
    printf("%d %d\n",M,N);
 
    return true;
}
 
int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论