QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302383#7954. Special NumbersPetroTarnavskyi#RE 1ms3608kbC++202.0kb2024-01-10 20:12:332024-01-10 20:12:35

Judging History

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

  • [2024-01-10 20:12:35]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3608kb
  • [2024-01-10 20:12:33]
  • 提交

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

output:


result: