結果

問題 No.1580 I like Logarithm！
コンテスト
ユーザー aperiodicmikan
提出日時 2021-07-02 22:42:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 3,180 bytes
コンパイル時間 1,833 ms
コンパイル使用メモリ 177,496 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-29 12:34:05
合計ジャッジ時間 4,683 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'll f(int, std::string)':
main.cpp:136:1: warning: no return statement in function returning non-void [-Wreturn-type]
  136 | }
      | ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,begin, end) for (ll i = begin; i < (ll)(end); i++)

using namespace std;
using ll = long long;
template<typename T>
using pqueueAsc = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using pqueueDesc = priority_queue<T, vector<T>, less<T>>;

template<typename T>
using vec2 = vector<vector<T>>;
template<typename T>
using vec3 = vec2<vector<T>>;
template<typename T>
using vec4 = vec3<vector<T>>;
template<typename T>
using vec5 = vec4<vector<T>>;
template<typename T>
using vec6 = vec5<vector<T>>;

int gcd(int a, int b){
    if(b == 0)return a;
    return gcd(b, a%b);
}
ll extGCD(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll g = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return g;
}
//ax+by=cをみたす整数x,y
bool solveLinearEquation2(ll a, ll b, ll c, ll &x, ll &y){
    if(c % gcd(a,b) != 0)return false;
    /*
        (a/d)X+(b/d)Y=c/d
        (a/d)x+(b/d)y=1
        (a/d)(c/d)x+(b/d)(c/d)y=c/d
        X=(c/d)x-k(b/d)
        Y=(c/d)y+k(a/d)
        必要に応じてkを決める
    */
    ll d = extGCD(a,b,x,y);
    ll k = 0;
    x = (c/d)*x-k*(b/d);
    y = (c/d)*y+k*(a/d);
    
    return true;
}
ll MOD = 1000000007;

vector<ll> mfact(1,1);

ll minv(ll a){
    ll x;ll y;
    extGCD(a, MOD, x, y);
    if(x<0){
        x+= ((-x)/MOD+1)*MOD;
        x %= MOD;
    }
    return x;
}

ll mpow(ll a,ll b){
    ll res = 1;
    while(b > 0){
        if(b%2==1)res=(res*a)%MOD;
        b/=2;
        a = (a*a)%MOD;
    }
    return res;
}

ll mfactorial(ll a){
    if(mfact.size()-1 >= a)return mfact[a];
    for(ll i = mfact.size();i<=a;i++){
        mfact.push_back((i * mfact[i-1])%MOD);
    }
    return mfact[a];
}

ll mcomb(ll n, ll r){
    return (((mfactorial(n) * minv(mfactorial(r)))%MOD) * minv(mfactorial(n-r)))%MOD;
}
ll ipow(ll a, ll b){
    ll res = 1;
    while(b > 0){
        if(b % 2 == 1)res*=a;
        a*=a;
        b/=2;
    }
    return res;
}

void factorize(map<ll,ll>& fac, vector<ll>& sieved, ll a){
    while(a != 1){
        if(fac.find(sieved[a]) == fac.end())fac[sieved[a]] = 0;
        fac[sieved[a]]++;
        a/=sieved[a];

    }
}
/**
 * エラトステネスのふるい
 * res[i]はiの最小の素因数
 */
void primesieve(vector<ll>& res,ll n){
    res = vector<ll>(n+1, -1);
    for(int i = 2;i <= n;i++){
        if(res[i] != -1)continue;
        res[i] = i;
        for(int j = 2;j*i <= n;j++){
            res[j*i] = i;
        }
    }
}
/**
 * ふるい->素数だけ取り出す
 */
vector<ll> primesuntil(ll n){
    vector<ll> res;
    vector<ll> sieved;
    primesieve(sieved, n);
    for(int i = 2;i <= n;i++){
        if(sieved[i] == i)res.push_back(i);
    }
    return res;
}

ll f(int A, string B){

}

int main(){
    int A;string B;cin>>A>>B;
    ll D = 0;
    for(int i = 0;i < B.size();i++){
        int c = B[B.size()-1-i]-'0';
        D += (c * mpow(A, i)) % MOD;
        D %= MOD;
    }
    ll res = ((B.size()-1) * ((D - mpow(A, B.size()-1) + MOD + 1 ) % MOD)) % MOD;
    rep(i,0,B.size()-1){
        res += (i*(A-1) * mpow(A,i)) % MOD;
        res %= MOD;
    }
    cout<<res<<endl;


}
0