URAL 1698 自守数

  1. 云栖社区>
  2. 博客列表>
  3. 正文

URAL 1698 自守数

prime7 2013-10-06 19:47:00 浏览531 评论0

摘要: 好吧 苟哥总结好了我直接粘了 自守数的定义   对于一个k位的自然数n,如果它的平方后的最后k位跟原数相同,那么n就叫做自守数。数学定义表达式为:。   一位数的自守数有三个,分别为1,5,6。

好吧 苟哥总结好了我直接粘了

自守数的定义

 

对于一个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;
}



【云栖快讯】阿里云栖开发者沙龙(Java技术专场)火热来袭!快来报名参与吧!  详情请点击

网友评论

prime7
文章209篇 | 关注0
关注
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
RDS是一种稳定可靠、可弹性伸缩的在线数据库服务。支持MySQL、SQL Server、Po... 查看详情
双12

双12