CF 345A Mike and Frog

题目

自己歪歪的做法WA了好多发。

原题中每一秒都相当于

$x1 = f1(x1)$

$x2 = f2(x2)$

然后这是一个定义域和值域都在[0,m-1]的函数，显而易见其会形成一个环。

而且环长不超过m，所以实际上问题就分为了两部分：

1.x1变到a1，x2变到a2（h -> a的长度）

2.x1做循环，x2做循环直到同时为a1，a2。（a -> a的长度）

我们设第一步分别用了m1 s, m2 s，第二步用了 t1 s ,t2 s。

对于第一部分我们可以直接枚举吗，因为长度不超过m。

对于第二部分实际上是两个式子。

$ans = △1 * t1 + m1$

$ans = △2 * t2 + m2$

这个式子只需要枚举就行了。因为m1，m2最多相差不超过m，而在最优决策下△1或△2绝对值每变化1，m1,m2必然至少变化1，所以△最大为m

问题解决，注意各种特判，比如都没有t值，有一个有t值，无解的情况。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#define LL long long

using namespace std;

LL m,ans;

LL gcd(LL a,LL b){

    if(!b) return a;

    return gcd(b,a%b);

}

/*

since the f(x) be an fuction from a num x to y.

so it may be a cricle.

*/

void solve(LL &ansv,LL &sumv){

    LL h,a,x,y,ans=;

    scanf("%I64d%I64d%I64d%I64d",&h,&a,&x,&y);

    for(int i=;i<=m;i++){

        h=(h*x%m+y)%m;

        if(h==a){

            ansv=(LL)i;    //how many seconds it would take for us to arrive 'a' from 'h'

            goto L;

        }

    }

    puts("-1");

    exit();

    L:h=a;

    sumv=-;

    for(int i=;i<=m;i++){

        h=(h*x%m+y)%m;    //how many seconds it would take for us to arrive 'a' from 'a'

        if(h==a){

            sumv=(LL)i;

            return;

        }

    }

}

/*

a1 + k1*a2 = b1 + k2*b2

ans = a1 (mod a2)

ans = b1 (mod b2)

*/

int main(){

    scanf("%I64d",&m);

    LL a1,a2,b1,b2;

    solve(a1,a2);

    solve(b1,b2);

    if(a1==b1) ans=a1;

    else if(a2==-&&b2==-){

        puts("-1");

        return ;

    }

    else if(a2==-&&a1>b1&&(a1-b1)%b2==) ans=a1;

    else if(b2==-&&b1>a1&&(b1-a1)%a2==) ans=b1;

    else if(a2==-||b2==-){

        puts("-1");

        return ;

    }

    else{

        LL k1;

        for(k1=;k1<=m;k1++)

            if((a1+k1*a2-b1)%b2==){

                ans=a1+k1*a2;

                if(ans>=b1) break;

            }

        if(k1>m) ans=-;

    }

    printf("%I64d\n",ans);

    return ;

}

Code

巴特西

CF 345A Mike and Frog

最新文章

热门文章