QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#302383 | #7954. Special Numbers | PetroTarnavskyi# | RE | 1ms | 3608kb | C++20 | 2.0kb | 2024-01-10 20:12:33 | 2024-01-10 20:12:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef __int128 LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int LOG = 20;
VI digits;
LL dpT1[LOG][2][2][2];
LL dp1(int pos, int prefd, int eq, int has1)
{
if(pos == SZ(digits))
return has1;
if(dpT1[pos][prefd][eq][has1] != -1)
return dpT1[pos][prefd][eq][has1];
int mx = 10;
if(eq)
mx = digits[pos] + 1;
LL res = 0;
FOR(cur, 0, mx)
res += dp1(pos + 1, prefd || (cur != 0), eq && (cur == digits[pos]), has1 || (prefd && (cur == 0)));
return dpT1[pos][prefd][eq][has1] = res;
}
map<LL, LL> dpT2[LOG][2];
LL dp2(int pos, int eq, long long k)
{
if(pos == SZ(digits))
return (k == 1);
if(dpT2[pos][eq].count(k))
return dpT2[pos][eq][k];
int mx = 10;
if(eq)
mx = digits[pos] + 1;
LL res = 0;
FOR(cur, 1, mx)
res += dp2(pos + 1, eq & (cur == digits[pos]), k / gcd(k, (long long)cur));
return dpT2[pos][eq][k] = res;
}
LL solve(LL k, __int128 n)
{
if(n == 0)
return 0;
digits.clear();
FOR(i, 0, LOG)
FOR(j, 0, 2)
{
FOR(l, 0, 2)
FOR(m, 0, 2)
dpT1[i][j][l][m] = -1;
dpT2[i][j].clear();
}
while(n)
{
digits.PB(n % 10);
n /= 10;
}
reverse(ALL(digits));
LL ans = dp1(0, 0, 1, 0);
ans += dp2(0, 1, k);
FOR(i, 1, SZ(digits))
ans += dp2(i, 0, k);
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
long long k;
string l, r;
cin >> k >> l >> r;
__int128 L = 0, R = 0;
FOR(i, 0, SZ(l))
L = 10 * L + (l[i] - '0');
FOR(i, 0, SZ(r))
R = 10 * R + (r[i] - '0');
LL ans = solve(k, R) - solve(k, L - 1);
int mod = 1e9 + 7;
cout << (int)(ans % mod) << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
5 1 20
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
5 50 100
output:
19
result:
ok single line: '19'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
15 11 19
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
1 100 100000
output:
99901
result:
ok single line: '99901'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 800 43021
output:
23570
result:
ok single line: '23570'
Test #7:
score: -100
Runtime Error
input:
1125899906842624 1 100000000000000000000