nyoj 52-无聊的小明 (模拟, SET)
2024-10-06 15:41:31
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位都相同。
众所周知,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 = ;
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 = ;
const int MAX = 0x3f3f3f3f;
int A[] = {, , , , , }; 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 = , my_begin, temp_n, my_end, flag = ;
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 = ;
break;
}
}
if(!flag)
printf("%lld\n", cnt);
else
printf("-1\n");
}
return ;
}
最新文章
- Python黑帽编程2.9 面向对象编程
- 用电脑给手机安装App
- Android 对话框(Dialog)大全 建立你自己的对话框
- Emmet (Zen Coding) HTML基本语法
- delete-by-query插件
- S.O.L.I.D
- [POJ] 2239 Selecting Courses(二分图最大匹配)
- 【转】 i2c驱动调试经验
- windows程序设计读书笔记1——创建窗口
- ListView.MultiChoiceModeListener
- SQL如何实现远程数据库链接
- 责任链模式 职责链模式 Chain of Responsibility Pattern 行为型 设计模式(十七)
- 主成分分析法PCA原理
- windows下运行Eigen
- db2look 工具
- LinkedList 实现 Queue
- 厉害了WORD大S
- iOS推送功能极光推送的介绍与实现
- Memcached服务器UDP反射放大攻击
- python匹配两个字符串中间的字符串