866
技術社區[雲棲]
URAL 1698 自守數
好吧 苟哥總結好了我直接粘了
自守數的定義
對於一個k位的自然數n，如果它的平方後的最後k位跟原數相同，那麼n就叫做自守數。數學定義表達式為：。
一位數的自守數有三個，分別為1，5，6。兩位數以上的自守數分為A、B兩類，A類是以5結尾，B類是以6結尾。
例如，以5結尾的自守數有25，625，90625等；以6結尾的自守數有76、376、9376等。
兩類自守數的一個基本性質是：相同位數的兩類自守數的和相加等於自守數的位數乘10再加上1，即：
5＋6=10＋1
25＋76=100＋1
625＋376=1000＋1
關於自守數的兩個重要的性質：
(1)一個數為自守數當且僅當它為一個自守數的後綴。
(2)（1除外）n位數的自守數僅有兩個（位數包括前導0）,優先考慮最高位不為0的時候。
一個數為自守數，那麼它的所有後綴均為自守數。所以所有位數大於1的自守數的末尾必定為5或6。
對於尾數為5或6這兩種自守數，每一種固定長度的自守數至多有1個。
自守數的計算方法：
一個k+1位的自守數F(k+1)可以由F(k)來求得，兩類數的計算方法不同。
A類：求F(k)的平方，取最後k+1位，若第k+1位是0，則取最後k+2位。
例如：
25*25 = 625，得625
6252 = 390625，得90625
8906252 = 793212890625，得2890625
B類：
求F(k)的平方，取最後k+1位，把最後k+1位的數用10減之代替，若第k+1位是0，則取最後k+2位來減，第k+1位保持為0。
例如：
762 = 5776，10-7 = 3，得376
93762 = 87909376，10-9 = 1，得109376
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define ll long long
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll phi(long long n)
{
long long rea=n;
for(int i=2; i*i<=n; i++)
if(n%i==0)
{
rea=rea-rea/i;
do
n/=i;
while(n%i==0);
}
if(n>1)rea=rea-rea/n;
return rea;
}
ll exp_mod(ll a,ll b,ll c)
{
a%=c;
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%c;
b>>=1,a=a*a%c;
}
return ans;
}
int main()
{
ll a,n;
cin>>a>>n;
if(gcd(a,n)!=1)
{
puts("0");
return 0;
}
ll p=phi(n),l=(ll)sqrt(p*1.0),ans=1e9;
for(ll i=1; i<=l; i++)
if(p%i==0)
{
if(exp_mod(a,i,n)==1)ans=min(ans,i);
if(exp_mod(a,p/i,n)==1)ans=min(ans,p/i);
}
printf("%I64d\n",ans);
return 0;
}
最後更新：2017-04-03 14:53:48