app应用下载网站源码,北京建设教育协会官网,移动互联网营销公司,专业做网站网络题目的意思大概就是问是否存在一串全是8的数字是L的倍数
直接想没有什么想法#xff0c;要想到用简洁的形式将这个数字表示出来#xff0c;对于每一位都是8的数字我们可以用 X8*(10k-1)/9的形式表示出来#xff0c;那么题目的意思就是求X使L|X#xff0c;我们先处理一下8和…题目的意思大概就是问是否存在一串全是8的数字是L的倍数
直接想没有什么想法要想到用简洁的形式将这个数字表示出来对于每一位都是8的数字我们可以用 X8*(10k-1)/9的形式表示出来那么题目的意思就是求X使L|X我们先处理一下8和L即除去他们的最大公约数然后就是L’|(10k-1)/9即就是10k-1|9L’我们用L’表示9L’
问题就转化成了要求10k-1%L’’010k1mod L’’(其实找的是在模L’剩余系中10的阶)
如果10和L’不互质那么10没有阶
由欧拉定理我们得知10f(L’’)1mod L’’因此阶一定是f(L’’)的因子其中f(n)代表的是n的欧拉函数因此我们从小到大查找欧拉函数值的所有因子直到找到阶
在这种思路下有如下代码
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e55;ll L;ll gcd(ll a,ll b)
{return b0?a:gcd(b,a%b);
}ll phi(ll x)
{ll ret1;for(ll i2;i*ix;i){if(x%i0){ret*(i-1);x/i;while(x%i0){ret*i;x/i;}}if(x1) break;}if(x1) ret*(x-1);return ret;
}ll mult(ll a,ll b,ll t)
{a%t; b%t;ll ret0;while(b){if(b1){reta; if(rett) ret-t;}a1; b1;if(at) a-t;}return ret;
}ll quick_pow(ll a,ll b,ll t)
{ll ret1;a%t;while(b){if(b1) retmult(ret,a,t);amult(a,a,t);b1;}return ret;
}int main()
{int Case0;while(~scanf(%lld,L) L){Case;ll tgcd(8,L);LL/t*9;ll ans;if(L%20 || L%50){ans0;}else{tphi(L);ans-1;//printf(t%lld\n,t);ll ttsqrt(t)1;for(ll i1;itt;i){if(t%i0 quick_pow(10,i,L)1){ansi;break;}}if(ans0)for(ll itt;i0;i--){if(t%i0 quick_pow(10,t/i,L)1){anst/i;break;}}}printf(Case %d: %lld\n,Case,ans);}return 0;
}这里求欧拉函数值的用了p为素数f(pk)(k-1)*pk-1。然后在遍历欧拉函数因子的时候用到一个技巧任何一个数的因子都可以和另一个因子相乘得到这个数这两个因子中一个大一个小小的一定小于等于sqrt(n)因此我们在查找因子的时候不要遍历1—n而是先遍历1—sqrt(n)查找较小的因子如果没有找到 再从sqrt(n)—1,查找相对应的较大的因子这样就将原来O(n)的复杂度降低为O(logn)的复杂度,十分巧妙
这里放一个优化版本的
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e55;ll L;ll gcd(ll a,ll b)
{return b0?a:gcd(b,a%b);
}ll phi(ll x)
{ll retx;for(ll i2;i*ix;i){if(x%i0){retret/i*(i-1);x/i;while(x%i0){x/i;}}if(x1) break;}if(x1) retret/x*(x-1);return ret;
}ll mult(ll x, ll y, ll p)
{long double d1;dd*x/p*y;return ((x*y-((ll)d)*p)%pp)%p;
}ll quick_pow(ll a,ll b,ll t)
{ll ret1;a%t;while(b){if(b1) retmult(ret,a,t);amult(a,a,t);b1;}return ret;
}int main()
{int Case0;while(~scanf(%lld,L) L){Case;ll tgcd(8,L);LL/t*9;ll ans;if(L%20 || L%50){ans0;}else{tphi(L);ans-1;//printf(t%lld\n,t);ll ttsqrt(t)1;for(ll i1;itt;i){if(t%i0 quick_pow(10,i,L)1){ansi;break;}}if(ans0)for(ll itt;i0;i--){if(t%i0 quick_pow(10,t/i,L)1){anst/i;break;}}}printf(Case %d: %lld\n,Case,ans);}return 0;
}主要优化了快速幂中long long 乘法部分和欧拉函数值的求值.
这里欧拉函数值的求法用到欧拉函数容斥原理求法.即 f(n)n∗(p1−1)/p1∗(p2−1)/p2∗.....∗(pk−1)/pkf(n)n*(p1-1)/p1*(p2-1)/p2*.....*(pk-1)/pkf(n)n∗(p1−1)/p1∗(p2−1)/p2∗.....∗(pk−1)/pk这里pi为n的素因子
