「Cfz Round 1」Dead Cells 题解

· · 个人记录

思路

由于每过 a 小时就会多一倍，每过 b 小时就会少一半，为两者公倍数时不变也等价于多一倍再减一半，所以在 a<b 的情况下，答案就是 2^{k/a-k/b}。

接下来考虑 a>b 的情况，乍一想答案肯定是 1，但是例如 a=5,b=2,k=5 这样的情况答案就为 2，原因是在最后一个 b 出现后 a 还能再出现一次，即 k\bmod a<k \bmod b，单独判断再输出即可。

最后时间复杂度 \mathcal O(\log (k/a-k/b))。

Code

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#define int long long
#define ull unsigned long long
using namespace std;
int a,b,k;
const int MOD=998244353;
int fpow(int di,int mi){
    if(mi==0)return 1;
    int tp=fpow(di,mi/2);
    if(mi%2==1)return tp%MOD*tp%MOD*di%MOD;
    return tp%MOD*tp%MOD;
}
signed main(){
    scanf("%lld%lld%lld",&a,&b,&k);
    int tmpa=k/a;
    int tmpb=k/b;
    int tmp=tmpa-tmpb;
    if(a>b){
        if(k%a<k%b)printf("2");
        else printf("1");
        return 0;
    }
    if(tmp<1){
        printf("%lld\n",1);
        return 0;
    }
    printf("%lld\n",fpow(2,tmp));
    return 0;
}