HDU 2462 The Luckiest number
2024-08-23 22:53:27
The Luckiest number
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2462
64-bit integer IO format: %I64d Java class name: Main
Chinese people think of '8' as the lucky digit. Bob also likes digit '8'. Moreover, Bob has his own lucky number L. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of L and consist of only digit '8'.
Input
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.
Output
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.
Sample Input
8
11
16
0
Sample Output
Case 1: 1
Case 2: 2
Case 3: 0
Source
解题:
首先,由题意可以得出,(10^x - 1)/ 9 * 8 = L * p(p是一个未知数,但必定是整数)。
然后对上式进行移项处理,得:(10^x - 1) = 9 * L * p / 8。
设m = 9 * L / gcd(L, 8),则有(10^x - 1) = m * p'。p’是必然存在的一个整数。
然后问题就转化成为了 10^x = 1(mod m),观察此式,显然,m和10必定互质。
于是根据欧拉定理,10^(Euler(m)) = 1(mod m) 。由于题目要求最小的解,解必然是Euler(m)的因子。
转自 OK_again
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int maxn = ;
LL mul(LL a, LL b, LL mod) {
LL ret = ;
while(b) {
if(b&) ret = (ret + a) % mod;
a = (a<<)%mod;
b >>= ;
}
return ret;
}
LL quickPow(LL base,LL index,LL mod){
LL ret = ;
while(index){
if(index&) ret = mul(ret,base,mod);
index >>= ;
base = mul(base,base,mod);
}
return ret;
}
bool np[maxn] = {true,true};
int p[maxn],tot;
void init(){
for(int i = ; i < maxn; ++i){
if(!np[i]) p[tot++] = i;
for(int j = ; j < tot && p[j]*i < maxn; ++j){
np[p[j]*i] = true;
if(i%p[j] == ) break;
}
}
}
LL Euler(LL n){
LL ret = n;
for(int i = ; (LL)p[i]*p[i] <= n; ++i){
if(n%p[i] == ){
ret = ret/p[i]*(p[i] - );
while(n%p[i] == ) n /= p[i];
}
}
if(n > ) ret = ret/n*(n-);
return ret;
}
vector<int>F;
void Fn(LL n){
F.clear();
for(int i = ; i < tot && n > ; ++i){
while(n%p[i] == ){
n /= p[i];
F.push_back(p[i]);
}
}
if(n > ) F.push_back(n);
}
int main(){
init();
LL L;
int cs = ;
while(scanf("%I64d",&L),L){
LL m = *L/__gcd(L,8LL);
if(__gcd(m,10LL) != ){
printf("Case %d: 0\n",cs++);
continue;
}
LL x = Euler(m);
Fn(x);
for(auto it:F)
if(quickPow(,x/it,m) == ) x /= it;
printf("Case %d: %I64d\n",cs++,x);
}
return ;
}
最新文章
- 按钮button的css样式(扁平化底色)
- Git 常用命令详解
- Linux 第05天
- python生成器实现杨辉三角
- Dynamic Percentage of Operands
- chromium的Backtrace记录
- MVC validation
- Mysql 定时备份操作
- (C#) 引用工程中发现有黄色叹号
- 第16讲- UI组件之TextView
- C#VS面向对象基础(二)
- openstack 源码分析
- SharePoint Search之(两)持续抓取Continues crawl
- 什么是DCI
- 内联元素于与块元素的转换 相对定位、绝对定位以及fixed定位 Z轴覆盖
- emqtt日志、证书、集群状态等位置
- filter in Servlet
- ubuntu 14.04 上配置vlc组播源
- Excel技巧--空白处补零
- .net core identity(一)简单运用