题目链接：https://atcoder.jp/contests/abc174/tasks/abc174_c
题意：n个7组成的数字 问为n最少为多少时 是 k的倍数， 若是不存在输出-1
思路： sum%k==0时满足条件， 有大数的时候应该很容易联想到取模，不断的大数取模 暴力跑一遍就行
猜也能猜到最大不会超过1e6
自己的代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define ull unsigned long long 5 #define pb push_back 6 const int maxn=2e5+10; 7 const int mod=1e9+7; 8 9 ll k; 10 11 ll power(ll base,ll n) 12 { 13 ll r=1; 14 while(n) 15 { 16 if(n%2) r=r*base%k; 17 base=base*base%k; 18 n/=2; 19 } 20 return r; 21 } 22 23 24 25 int main() 26 { 27 ios::sync_with_stdio(false); 28 cin.tie(0); 29 cin>>k; 30 ll sum=0; 31 int len=1; 32 while(1) 33 { 34 sum+=power(10,len-1)*7; 35 sum%=k; 36 if(sum%k==0) 37 { 38 cout<<len<<‘\n‘; 39 return 0; 40 } 41 len++; 42 if(len>1e6) 43 { 44 cout<<-1<<‘\n‘; 45 return 0; 46 } 47 } 48 49 50 51 }
别人的代码，很容易看出每个数如果存在解的话肯定不会超过k 因为取模后的数为0~k-1 k个数， 当第k+1次时，至少会有2个数是相同的，此时循环节就出现了
看下面的代码很容易看出 当sum相同时 就是循环节
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define pb push_back 5 const int maxn =2e5+10; 6 const int mod=1e9+7; 7 8 9 10 int main() 11 { 12 ios::sync_with_stdio(false); 13 cin.tie(0); 14 int k; 15 cin>>k; 16 int sum=0; 17 int len=1; 18 while(1) 19 { 20 sum=sum*10+7; 21 sum%=k; 22 if(sum==0) 23 { 24 cout<<len<<‘\n‘; 25 return 0; 26 } 27 if(len>k) 28 { 29 cout<<-1<<‘\n‘; 30 return 0; 31 } 32 len++; 33 } 34 35 36 }
AtCoder Beginner Contest 174 C - Repsept
原文：https://www.cnblogs.com/winfor/p/13424026.html
