题解 | #云哥教你学数学！#

感谢巨巨们给面子都在写我的签到orz
这个题很明显就是一个求丑数和一个类似与斐波那契数列的一个签到题。我们只需要注意丑数的最大值和对于项数较大的斐波那契怎么求解即可。
其实就是丑数筛和矩阵快速幂，巨巨们大多数wa的原因可能就是没有开int128
这里给出题解

#include<iostream>
#include<algorithm>
#define _for(i) for(int i=0;i<2;i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=2;
const int mod=1e9+7;
ll s[N];
void ptr(__int128_t x){
    if(x>9)ptr(x/10);
    putchar('0'+x%10);
}
void cou(int a,int b){
    ll f2=1,f3=1,f5=1;
    __int128_t f[50010]={0,1};
    for(int i=2;i<=b;i++){
        __int128_t t=f[f2]*2;
        t=min(t,f[f3]*3);
        t=min(t,f[f5]*5);
        if(t>=f[f2]*2)f2++;
        if(t>=f[f3]*3)f3++;
        if(t>=f[f5]*5)f5++;
        f[i]=t;
    }
    s[0]=f[b]%mod;s[1]=f[a]%mod;
}
void pow(ll t[N][N]){
    ll tt[N][N]={0};
    _for(i)
        _for(j)
            _for(k)
                tt[i][j]=(tt[i][j]+t[i][k]*t[k][j])%mod;
    _for(i)
        _for(j)
            t[i][j]=tt[i][j];
}
void add(ll a[N][N],ll b[N][N]){
    ll t[N][N]={0};
    _for(i)
        _for(j)
            _for(k)
                t[i][j]=(t[i][j]+a[i][k]*b[k][j])%mod;
    _for(i)
        _for(j)
            a[i][j]=t[i][j];
}
void pow(int n){
    ll t[N][N]={2,1,3,0},aa[N][N]={2,1,3,0};
    while(n){
        if(n&1)add(aa,t);
        pow(t);
        n>>=1;
    }
    cout<<(s[0]*aa[0][0]+s[1]*aa[1][0])%mod;
}
int main(){
    int a,b,n;
    cin>>a>>b>>n;
    cou(a,b);
    if(n==1)cout<<s[1];
    else if(n==2)cout<<s[0];
    else {n-=3;pow(n);}
}