好吧 苟哥总结好了我直接粘了
自守数的定义
对于一个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;
}
