本文主要是介绍POJ 3696/ HDU 2462 The Luckiest number (数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：LINK
给定一个数L, 求使得k*L ==8...8(一串8) 求这一串8的最小长度.
对于8.....8可以写成 (10^x -1)*8/9
即 (10^x - 1)*8/9 = k*n
(10^x - 1)* 8 / gcd(8, n) = 9*n*k/gcd(8,n) ;
令p = 8/gcd(8,n); q = 9*n/gcd(8,n); 这里p,q互质
因此(10^x - 1) 是 q的整数倍
可以得到 10^x = 1 (mod q)
只要求得最小的x(x>0) 满足上面的式子就可以了
这里有两种方法 1),利用欧拉定理: 当gcd(a,b)==1时，a^φ(b)≡1(mod b); 如果gcd(10,q) != 1 无解.否则解为φ(q) 的因子(拉格朗日定理) ,我们可以处理出来φ(q)的所有因子，依次进行判断即可.
2),对于求解 a^x = b (mod c)，我们可以采用BSGS算法(我直接套模板) .
1)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define INF 1000000000
typedef __int64 LL;
#define N 2000000002
#define M 100005
LL n;
vector<LL > save, fac, allfac;
LL cou[100];
bool prime[M];
LL gcd(LL a, LL b)
{if(!b) return a;return gcd(b, a%b);
}
LL eular(LL n)
{LL ret = 1;for(LL i=2; i*i<=n; i++) {if(n%i ==0) {n /= i;ret *= (i-1);while(n%i == 0) {n /= i; ret *= i;}}}if(n>1) ret *= (n-1) ;return ret;
}
LL mul(LL x, LL y, LL mod)
{LL ret = 0;while(y ) {if(y&1) {ret += x; ret %= mod;}y >>= 1;x += x; x %= mod;}return ret;
}
LL pow_(LL x, LL y, LL mod)
{LL ret = 1;while(y) {if(y&1) {ret = mul(ret, x, mod);}y >>= 1;x = mul(x, x, mod);}return ret ;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEint time = 0;while(scanf("%I64d", &n), n) {LL tmp = n*9/gcd(8, n);printf("Case %d: ", ++time);if(gcd(10, tmp) != 1) {printf("0\n");continue;}LL pp = eular(tmp);allfac.clear();for(LL i = 1; i*i <=pp; i++) {if(pp % i == 0) {allfac.push_back(i);allfac.push_back(pp/i);}}sort(allfac.begin(), allfac.end());for(int i = 0; i < allfac.size(); i++) {LL gg = pow_(10, allfac[i], tmp);if(gg == 1) {printf("%I64d\n", allfac[i]);break;}}}return 0;
}2)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define INF 1000000000
typedef __int64 LL;
const LL maxn = 65535;
struct hash
{LL a,b,next;
} Hash[maxn << 1];
LL flg[maxn + 66];
LL top,idx;
void ins(LL a,LL b)
{LL k = b & maxn;if(flg[k] != idx){flg[k] = idx;Hash[k].next = -1;Hash[k].a = a;Hash[k].b = b;return ;}while(Hash[k].next != -1){if(Hash[k].b == b) return ;k = Hash[k].next;}Hash[k].next = ++ top;Hash[top].next = -1;Hash[top].a = a;Hash[top].b = b;
}
LL find(LL b)
{LL k = b & maxn;if(flg[k] != idx) return -1;while(k != -1){if(Hash[k].b == b) return Hash[k].a;k = Hash[k].next;}return -1;
}
LL gcd(LL a,LL b)
{return b?gcd(b,a%b):a;
}
LL ext_gcd(LL a,LL b,LL& x,LL& y)
{LL t,ret;if (!b){x=1,y=0;return a;}ret=ext_gcd(b,a%b,x,y);t=x,x=y,y=t-a/b*y;return ret;
}
LL Inval(LL a,LL b,LL n)
{LL x,y,e;ext_gcd(a,n,x,y);e=(LL)x*b%n;return e<0?e+n:e;
}
LL mul(LL x, LL y, LL mod)
{LL ret = 0;while(y ) {if(y&1) {ret += x; ret %= mod;}y >>= 1;x += x; x %= mod;}return ret;
}
LL pow_(LL x, LL y, LL mod)
{LL ret = 1;while(y) {if(y&1) {ret = mul(ret, x, mod);}y >>= 1;x = mul(x, x, mod);}return ret ;
}
LL BabyStep(LL A,LL B,LL C)
{top = maxn;++ idx;LL buf=1%C,D=buf,K;LL i,d=0,tmp;//buf = buf *A%C;for(i=0; i<=100; buf=buf*A%C,++i)if(buf==B)return i;while((tmp=gcd(A,C))!=1){if(B%tmp)return -1;++d;C/=tmp;B/=tmp;D=D*A/tmp%C;}LL M=(LL)ceil(sqrt((double)C));for(buf=1%C,i=0; i<=M; buf=buf*A%C,++i)ins(i,buf);for(i=0,K=pow_((LL)A,M,C); i<=M; D=D*K%C,++i){tmp=Inval((LL)D,B,C);LL w ;if(tmp>=0&&(w = find(tmp)) != -1){if(i*M+w+d<=0) continue;//printf("%I64d \n", i*M + w+ d);return i*M+w+d;}}return -1;
}
LL eular(LL n)
{LL ret = 1;for(LL i=2; i*i<=n; i++) {if(n%i ==0) {n /= i;ret *= (i-1);while(n%i == 0) {n /= i; ret *= i;}}}if(n>1) ret *= (n-1) ;return ret;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGELL time = 0;LL n;while(scanf("%I64d", &n), n) {LL tmp = n*9/gcd(8, n);printf("Case %d: ", ++time);//10^X ==1 MOD tmpLL ans = BabyStep(10LL, 1LL, tmp);if(ans<0) {printf("0\n"); continue;}if(ans>0) {printf("%I64d\n", ans);}LL P = tmp, A = 10, D = 1;LL x = eular(P);if(pow_(A, ans + x, P) != D) {printf("0\n"); continue;}LL x1 = x;for(LL i = 2; i * i<= x1; i++) {if(x1 % i ==0) {while(x1 % i == 0) x1 /= i;while(x%i==0 && pow_(A, ans + x/i, P)==D) x/=i;}}if(x1 != 1) {while(x % x1 ==0 && pow_(A, ans + x/x1, P) ==D) x/=x1;}printf("%I64d\n", ans + x);}return 0;
}这篇关于POJ 3696/ HDU 2462 The Luckiest number (数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
