题目描述
路人甲给你出了一道奇怪的问题,他给你了一个正整数L,他想知道当正整数m,n为何值时,L^m与L^n的最后K位数字相同。
路人甲考虑到可能会有很多组解,你只需要告诉他最小的m,n且0<n<m。
输入格式
一个正整数L,一个正整数k
输出格式
输出一个最小的m,n
样例输入
:
100 3
样例输出:3 2
注释
【数据规模及约定】
100<=L<=9999
1<=k<=4
题解
数据有错,第八个点答案为103 3.
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define ll long long using namespace std; ll l,k,mod; int a[10002]; bool pd[10002]; void work() { ll s=l%mod,v=l%mod; int i; pd[s]=1; a[s]=1; for(i=2;i<=100000;i++) {s=(s*v)%mod; if(pd[s]) {printf("%d %d\n",i,a[s]); return ;} a[s]=i; pd[s]=1; } } int main() { scanf("%lld%lld",&l,&k); mod=pow(10,k); work(); return 0; }