QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#505266#9139. Prefix Divisible by Suffixucup-team2307TL 4877ms3972kbC++173.5kb2024-08-05 00:14:252024-08-05 00:14:26

Judging History

你现在查看的是最新测评结果

  • [2024-08-05 00:14:26]
  • 评测
  • 测评结果:TL
  • 用时:4877ms
  • 内存:3972kb
  • [2024-08-05 00:14:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int mod = 998244353;

ll solve_slow(ll n, ll c) {
    ll ans = 0;
    for(ll i = 1; i <= n; i++) {
        int ok = 0;
        for(ll tail = 10; tail <= i; tail*=10) {
            ll top = i / tail;
            if(tail == 10 || (i % tail) >= (tail/10))
                ok |= top % (i % tail + c) == 0;
        }
        // if(ok > 1) cout << i << " " << ok << endl;
        ans += ok;
    }
    return ans;
}

ll count(ll n, ll d) {
    return max(0ll, n / d);
}
ll solve2(ll n, ll c) {
    ll ans = 0;
    for(ll tail = 0; tail <= n; tail++) {
        ll len = to_string(tail).size();
        ll step = pow(10, len);
        ll mx = (n - tail) / step;
        ans += count(mx, (tail + c));
    }
    return ans;
}

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = euclid(b, a % b, y, x);
	return y -= a/b * x, d;
}
ll mod_inv(ll r, ll m) {
    ll x, y;
    euclid(r, m, x, y);
    x = (x%m+m)%m;
    // cout << r << " " << m << endl;
    assert(x*r%m == 1);
    return x;
}

ll crt(ll a, ll m, ll b, ll n) {
	if (n > m) swap(a, b), swap(m, n);
	ll x, y, g = euclid(m, n, x, y);
	if((a - b) % g != 0) return -1;
	x = (b - a) % n * x % n / g * m + a;
	return x < 0 ? x + m*n/g : x;
}

ll solve3(ll n, ll c) {
    const int D = 20;
    array<int, D> pref, P10;
    for(int i = 0; i < D; i++) P10[i] = pow(10, i);
    ll ans = 0;
    for(ll tail = 0; tail*tail <= n; tail++) {
        auto me = to_string(tail); reverse(all(me));
        for(int i = 0; i <= me.size(); i++) {
            pref[i] = tail % P10[i+1];
        }
        ll len = me.size();
        ll step = pow(10, len);
        ll mx = (n - tail) / step;
        ll res = 0;
        for(int msk = 0; msk < 1<<(len-1); msk++) [&]{
            ll cur = tail + c, rem = 0;
            for(int i = 0; i < len - 1; i++) if((msk>>i)&1) {
                if(i && me[i] == '0') return;//invalid mask
                // cur = lcm(cur, pref[i] + c);
                // x * 10^(len - i - 1) + (tail / P10[i+1]) == 0 (mod pref[i] + c)
                ll D = P10[len - 1 - i], R = -(tail/P10[i+1]), M = pref[i] + c;
                R = (M+R%M)%M;

                ll g = __gcd(D, M);
                if(R % g != 0) return;
                R /= g;
                M /= g;
                D /= g;

                if(M > 1) {
                    R = R * mod_inv(D, M) % M;

                    // reqs.push_back({R, M});
                    // cout << rem << " = " << cur << ", " << R << " = " << M << endl;
                    rem = crt(rem, cur, R, M);
                    cur = lcm(cur, M);
                    // cout << M << " " << R << " : " << rem<< endl;
                    if(rem == -1) return;
cur = min(cur, ll(1e13));
                }
            }
            // cout << msk << " -- " << rem << " " << cur << " " << mx << " | " << count(mx - rem, cur)  << endl;
            res += count(mx - rem + (rem ? cur : 0), cur) * (__builtin_popcount(msk)&1 ? -1 : 1);
        }();
        // cout << tail << " " << res << " " << mx << endl;
        ans += res;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    ll n, c;
    cin >> n >> c;
    // while(solve3(n, c) == solve_slow(n, c)) n++;
    cout << solve3(n, c) << endl;

}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3928kb

input:

20 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

111 4

output:

9

result:

ok 1 number(s): "9"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

1111 10

output:

75

result:

ok 1 number(s): "75"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

1000000 7

output:

111529

result:

ok 1 number(s): "111529"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

1 1

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

99999 10000

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

1000 1

output:

287

result:

ok 1 number(s): "287"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

10000000 1

output:

3102010

result:

ok 1 number(s): "3102010"

Test #9:

score: 0
Accepted
time: 4ms
memory: 3904kb

input:

100000000 1

output:

31035571

result:

ok 1 number(s): "31035571"

Test #10:

score: 0
Accepted
time: 53ms
memory: 3924kb

input:

1000000000 1

output:

310375697

result:

ok 1 number(s): "310375697"

Test #11:

score: 0
Accepted
time: 202ms
memory: 3956kb

input:

10000000000 1

output:

3103907933

result:

ok 1 number(s): "3103907933"

Test #12:

score: 0
Accepted
time: 1306ms
memory: 3972kb

input:

100000000000 1

output:

31039265058

result:

ok 1 number(s): "31039265058"

Test #13:

score: 0
Accepted
time: 4877ms
memory: 3892kb

input:

1000000000000 1

output:

310394177863

result:

ok 1 number(s): "310394177863"

Test #14:

score: -100
Time Limit Exceeded

input:

10000000000000 1

output:


result: