当前位置: 代码迷 >> 综合 >> poj 3696 The Luckiest number 欧拉函数在解a^x=1modm的应用
  详细解决方案

poj 3696 The Luckiest number 欧拉函数在解a^x=1modm的应用

热度:15   发布时间:2024-01-19 05:39:37.0

题意:

给一个L,求长度最小的全8数满足该数是L的倍数。

分析:

转化为求方程a^x==1modm。之后就是各种数学论证了。

代码:

//poj 3696
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll L;
ll factor[65536];ll mul(ll x,ll y,ll p)
{ll ret=0;while(y){if(y&1)ret=(ret+x)%p;x=(x+x)%p;y>>=1;}return ret;
}ll pow(ll x,ll n,ll m)
{ll ret=1;x%=m;while(n){if(n&1)ret=mul(ret,x,m);x=mul(x,x,m);n>>=1;}return ret;
}ll euler(ll n)
{ll ret=n;for(ll i=2;i*i<=n;++i)if(n%i==0){ret=ret/i*(i-1);while(n%i==0)n/=i;}if(n>1)ret=ret/n*(n-1);return ret;	
}ll cal()
{ll m=L*9;for(int i=0;i<3;++i)if(m%2==0)m/=2;elsebreak;	if(m%2==0||m%5==0)return 0;ll phi=euler(m);int idx=0;for(ll i=1;i*i<=phi;++i)if(phi%i==0)factor[idx++]=i,factor[idx++]=phi/i;	sort(factor,factor+idx);for(int i=0;i<idx;++i)if(pow(10,factor[i],m)==1)return factor[i];
}int main()
{int cases=0;while(scanf("%I64d",&L)==1&&L){printf("Case %d: ",++cases);printf("%I64d\n",cal());}	return 0;	
} 


  相关解决方案