AOJ 778.乘积为n个1的数字游戏

203

题目



Description  


两位计算机爱好者在进行“积为n个1的数字游戏”,其中一位给定一个正整数p(约定整数p为个位数字不是5的奇数),另一位寻求正整数q,使得p与q之积全是1组成的整数。



Input  


第1行是测试数据的组数t,每组测试数据占1行,每行包括一个个位数字不是5的奇数p。


Output  


对应每组测试数据输出共1行,每行输出两个整数,之间有一个空格分隔,一个是满足条件的整数q, 另一个是p与q之积的1的个数,输入数据保证一定有解,如果有多组解,请输出1最少的一个解。


Sample Input  


3
11
9
89


Sample Output  


1 2
12345679 9
124843945068664169787765293383270911360799 44


题解


看着是高精度计算,但是模拟下可以发现不需要高精度计算
只需要提取出高精度计算的除法的一部分即可

如果能除尽就代表已经找到了答案,否则就将余数乘 101 当作被除数
如此循环下去

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com
 
かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;
 
 
 
void Do() {
    int p;
    scanf("%d",&p);
    int k;
    int a = 0;
    bool flag = false;
    for(k = 1;;k++) {
        a = a * 10 + 1;
        if(a < p) {
            if(flag)
            printf("0");
                continue;
        }
        int b = a / p;
        int c = a % p;
        printf("%d",b);
        flag = true;
        if(c == 0) {
            printf(" %d\n",k);
            break;
        }
        a = c;
    }
}
 
int main() {
    int T;
    scanf("%d",&T);
    while(T--)
        Do();
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论