蓝桥杯 adv237 三进制数位和

蓝桥杯 adv237 三进制数位和

题目描述

给定 L 和 R,你需要对于每一个6位三进制数(允许前导零),计算其每一个数位上的数字和,设其在十进制下为S。 一个三进制数被判断为合法,当且仅当S为质数,或者S属于区间[L,R]。 你的任务是给出合法三进制数的个数。

输入格式

一行两个非负整数 L,R。

输出格式

一行一个非负整数表示答案。

样例输入

0 0

样例输出

330

数据规模和约定

保证0<=L<R<=12。

参考解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <memory.h>

using namespace std;

bool prime[12]; // 6 位三进制数,数位之和最多为 12

void generatePrime() { // 埃拉托斯散筛法
memset(prime, true, sizeof(prime));
prime[0] = false;
prime[1] = false;
for (int i = 2; i < 4; i++) { // i < sqrt(12)
if (!prime[i])
continue;

for (int j = i * i; j < 12; j += i)
prime[j] = false;
}
}

int main() {
int l, r, ans = 0;
cin >> l >> r;

generatePrime();

for (int i = 0; i < 729; ++i) {
int sum = 0, j = i;
while(j) {
sum += j % 3;
j /= 3;
}
if (prime[sum] || (l <= sum && sum <= r))
++ans;
}
cout << ans << endl;
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×