3124: [Sdoi2013]直径
3108: [cqoi2013]图的逆变换

3122: [Sdoi2013]随机数生成器

高橋直樹 posted @ 2013年4月15日 19:51 in BZOJ with tags SDOI bzoj , 1762 阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=3122

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391145 Liu_Ts 3122 Accepted 9100 kb 1488 ms C++ 2158 B 2013-04-15 17:39:23

 

题意

已知Xi+1=(aXi + b)mod p;

给定X1,a,b,p(质数),t

求第一个满足Xn=t的n

题解

把原式化开,得

Xn=[a^(n-1)*X1+b*(a^(n-2)+a^(n-3)+..+a^0)]mod p;

分情况讨论

①X1=t时,ans=1;

②a=0时,

    1.b=t时,ans=2;

    2.b!=t时,ans=-1;

③a=1时,

    Xn=[X1+b*(n-1)]mod p=t

    移向之后,相当于求xb+yp=(t-X1)mod p;

    扩展gcd,ans=x+1;

④a>1时,

    Xn=[a^(n-1)*X1+b*(a^(n-1)-1)/(a-1)]mod p

    设c=(a-1)在模p意义下的逆元,即c=(a-1)^(p-2);

    Xn=[a^(n-1)*X1+bc*(a^(n-1)-1)]mod p

    化简得Xn=[(X1+bc)*a^(n-1)-bc]mod p=t

    令q=X1+bc,t`=(t+bc)mod p,

    移向后相当于求[q*a^(n-1)]mod p=t'

    接下来我的做法是,先求xq+yp=t'的解x;

    问题变为求a^x` mod p=x,ans=x`+1。就和山东11年的计算器那题一样了。

 

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<climits>
using namespace std;
typedef long long ll;
const int H=1000001;
int f[H],r[H];
ll p,a,b,x1,x,y,t;
 
ll km(ll a,ll k)
{
    if(!a) return 0;
    ll t=a,q=1;
    while(k)
    {
        if(k&1) q=((q%p)*(t%p))%p;
        t=((t%p)*(t%p))%p;
        k=k>>1;
    }
    return q;
}
void gcd(ll a,ll b,ll c)
{
    if(!b)
        if(!(c%a))
        {
            x=c/a;y=0;
            return;
        }
        else
        {
            x=-1;return;
        }
    gcd(b,a%b,c);
    if(x==-1) return;
    ll t=y;y=x-((a/b)*y);x=t;
}
       
void work1()
{
    t=(t-x1+p)%p;
    x=y=0;
    gcd(b,p,t);
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
        x++;
    }
    printf("%lld\n",x);
}
void work2()
{
    ll c=km(a-1,p-2);
    t=(t+((b*c)%p))%p;
    ll q=(x1+((b*c)%p))%p;
    x=y=0;
    gcd(q,p,t);
    if(x==-1)
    {
        puts("-1");return;
    }
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
    }
    int m=int(floor(sqrt(p)+1)),b=km(a,p-1-m);;
    memset(f,255,sizeof(f));
    memset(r,255,sizeof(r));
    ll now=1;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1) h=(h+1)%H;
        f[h]=now;r[h]=i;now=now*a%p;
    }
    now=x%p;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1)
        {
            if(f[h]==now)
            {
                printf("%d\n",i*m+r[h]+1);
                return;
            }
            h=(h+1)%H;
        }
        now=now*b%p;
    }
    puts("-1");
}
 
void work()
{
    if(x1==t){puts("1");return;}
    if(a==0)
    {
        if(b==t) puts("2");
        else puts("-1");
        return;
    } 
    if(a==1)
    {
        work1();
        return;
    }
    work2();
}
     
int main()
{
    int T;scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
        work();
    }
}
seo service london 说:
2024年2月22日 16:55

There are several dissertation web sites on the net once you locate unsurprisingly explained in the website


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter