52 - 无聊的小明
内存限制: 64MB 时间限制: 3000ms Special Judge: No
accepted:1 submit:3
题目描述:
这天小明十分无聊, 没有事做, 但不甘于无聊的小明聪明的想到一个解决无聊的办法, 因为他突然对数的正整数次幂产生了兴趣.
众所周知, 2 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6...... 我们说 2 的正整数次幂最后一位的循环长度是 4(实际上 4 的倍数都可以说是循环长度, 但我们只考虑最小的循环长度). 类似的, 其余的数字的正整数次幂最后一位数也有类似的循环现象.
这时小明的问题就出来了: 是不是只有最后一位才有这样的循环呢? 对于一个整数 n 的正整数次幂来说, 它的后 k 位是否会发生循环? 如果循环的话, 循环长度是多少呢?
注意:
1. 如果 n 的某个正整数次幂的位数不足 k, 那么不足的高位看做是 0.
2. 如果循环长度是 L, 那么说明对于任意的正整数 a,n 的 a 次幂和 a + L 次幂的最后 k 位都相同.
输入描述:
第一行输入一个整数 N(0<n<10); 接下来每组测试数据输入只有一行, 包含两个整数 n(1 <= n <100000) 和 k(1 <= k <= 5),n 和 k 之间用一个空格隔开, 表示要求 n 的正整数次幂的最后 k 位的循环长度.
输出描述:
每组测试数据输出包括一行, 这一行只包含一个整数, 表示循环长度. 如果循环不存在, 输出 - 1.
样例输入:
复制 1 32 2
样例输出:
4
分析:
ps:
1, 是存在结果不循环这种情况
2,emmmmmm, 数据超过 int, 用 long long 才可以 AC
1, 因为题目要求的是最后 k 位是否循环, 所以在做相乘的时候自需要取出最后 k 位的数与给定的数 n 相乘
2, 如果在最后取出的数与不是第一位的数位对应上的数相等了, 说明只存在局部循环, 不存在全局循环 (这就是跳出循环的条件,<set > 判重)
核心代码:
- while(my_begin != my_end)
- {
- temp *= n;
- my_end = temp % A[k];
- temp = my_end;
- my_set.insert(temp);
- if(!pr.second)
- {
- flag = 1;
- break;
- }
- }
C/C++ 代码实现 (AC):
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cmath>
- #include <stack>
- #include <map>
- #include <queue>
- #include <set>
- using namespace std;
- const int MAXN = 10010;
- const int MAX = 0x3f3f3f3f;
- int A[7] = {1, 10, 100, 1000, 10000, 100000};
- int main()
- {
- int t;
- scanf("%d", &t);
- while(t --)
- {
- set <long long> my_set;
- pair <set <long long> ::iterator, bool> pr;
- long long n, k, cnt = 0, my_begin, temp_n, my_end, flag = 0;
- scanf("%d%d", &n, &k);
- temp_n = n, my_begin = n % A[k];
- while(my_begin != my_end)
- {
- cnt ++;
- temp_n *= n;
- my_end = temp_n % A[k];
- temp_n = my_end;
- pr = my_set.insert(temp_n);
- if(!pr.second)
- {
- flag = 1;
- break;
- }
- }
- if(!flag)
- printf("%lld\n", cnt);
- else
- printf("-1\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2622788.html