NC51046. The Luckiest number
描述
输入描述
The input consists of multiple test cases. Each test case contains exactly one line containing L(1 ≤ L ≤ 2,000,000,000).
The last test case is followed by a line containing a zero.
输出描述
For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the length of Bob's luckiest number. If Bob can't construct his luckiest number, print a zero.
示例1
输入:
8 11 16 0
输出:
Case 1: 1 Case 2: 2 Case 3: 0
C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 492K, 提交时间: 2020-06-01 09:51:18
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll L;
ll p;
ll gcd(ll x,ll y) {
return y?gcd(y,x%y):x;
}
ll fastpow(ll x) {
ll ans=1,q=10;
while(x>0) {
if(x&1)ans=(ans*q)%p;
q=(q*q)%p;
x=x/2;
}
return ans%p;
}
ll phi(ll n) {
ll ans=n;
for(int i=2; i<=sqrt(n); i++)
if(n%i==0) {
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)ans=ans/n*(n-1);
return ans;
}
ll solve() {
ll d=gcd(9*L,8LL);
ll y=9*L/d;
p=y;
ll t=phi(y);
if(gcd(y,10LL)!=1)return 0;
ll s=sqrt(t);
for(int i=1; i<=s; i++)
if(t%i==0&&fastpow(i)==1)return i;
for(int i=s-1; i; i--)
if(t%i==0&&fastpow(t/i)==1)return t/i;
return 0;
}
int main() {
int id=0;
while(cin>>L&&L) {
id++;
printf("Case %d: %lld\n",id,solve());
}
return 0;
}
C++(clang++11) 解法, 执行用时: 22ms, 内存消耗: 376K, 提交时间: 2021-04-12 19:50:49
#include<bits/stdc++.h>
using namespace std;
int main() {
int l,t=0;
while(~scanf("%d",&l))
{
if(l==0) break;
long long f=8,ans=0;
for(int i = 1;i <= 1000000;i++)
{
if(f%l==0){ ans = i; break; }
f %= l;
f = f*10+8;
}
printf("Case %d: %d\n",++t,ans);
}
return 0;
}