QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#505266 | #9139. Prefix Divisible by Suffix | ucup-team2307 | TL | 4877ms | 3972kb | C++17 | 3.5kb | 2024-08-05 00:14:25 | 2024-08-05 00:14:26 |
Judging History
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