这不是家庭作业问题。我只是对这个问题很好奇。我的方法很简单：-)
我的蛮力C++代码：
int main()
{
ll l,r;
cin>>l>>r;
ll f=0;
ll i=l;
while(i<=r)
{
ll j=0;
string s;
ll c=0;
s=to_string(i);
// cout<<s<<" ";
ll x=s.length();
if(x==1)
{
c=0;
}
else
{
j=0;
//whil
while(j<=x-2)
{
string b,g;
b="1";
g="1";
b=s[j];
g=s[j+1];
ll k1,k2;
k1=stoi(b);
k2=stoi(g);
if(__gcd(k1,k2)==1)
{
c=1;
break;
}
j++;
}
}
ll d=0;
j=0;
while(j<=x-1)
{
if( s[j]=='2' || s[j]=='3' || s[j]=='5' || s[j]=='7')
{
string b;
b="1";
b=s[j];
ll k1=stoi(b);
if(i%k1==0)
{
//d=0;
}
else
{
d=1;
break;
}
}
j++;
}
if(c==1 || d==1)
{
// cout<<"NO";
}
else
{
f++;
// cout<<"PR";
}
// cout<<"n";
i++;
}
cout<<f;
return 0;
}
您将获得 2 个整数"L"和"R"。您需要在"L"到"R"范围内找到所有 PR 编号的计数(包括"L"到"R")。PR 编号是满足以下属性的数字：
没有一对相邻数字是互质数，
- PR 编号
即 PR 编号中的相邻数字不会相互互质。
可被 PR 编号中作为数字出现的所有个位数质数整除。
注意：如果 gcd(a，b)=1，则两个数字 'a' 和 'b' 是互质数。
另外，gcd(0，a)=a;
示例：
输入：[2,5].
输出："4"。(注意："1"不是质数，尽管它很常见)
(所有整数："2"，"3"，"4"，"5")满足PR号码的条件：-)
对"L"、"R"的约束：1 <= L, R <= 10^18
解决这个问题最有效的算法是什么？
注意：这只会解决第 1 部分，即 没有一对相邻数字是互质数，即 PR 编号中的相邻数字不会相互互质。
这是python中一个建设性的方法：我们不是遍历范围内的所有数字并按条件过滤，而是构造满足条件的所有数字。请注意，如果我们有一个有效的数字序列，为了继续有效，只有最右边的数字才重要，以便决定下一个数字是什么。
def ways(max_number, prev_digit, current_number):
if current_number > max_number:
return 0
count = 1
if prev_digit == 0:
if current_number != 0:
count += ways(max_number, 0, current_number * 10)
for i in range(2, 10):
count += ways(max_number, i, current_number * 10 + i)
if prev_digit == 2 or prev_digit == 4 or prev_digit == 8:
for i in [0, 2, 4, 6, 8]:
count += ways(max_number, i, current_number * 10 + i)
if prev_digit == 3 or prev_digit == 9:
for i in [0, 3, 6, 9]:
count += ways(max_number, i, current_number * 10 + i)
if prev_digit == 5 or prev_digit == 7:
count += ways(max_number, 0, current_number * 10)
count += ways(max_number, prev_digit, current_number * 10 + prev_digit)
if prev_digit == 6:
for i in [0, 2, 3, 4, 6, 8, 9]:
count += ways(max_number, i, current_number * 10 + i)
return count
由于我们正在生成所有有效数字，最多 max_number 个，没有任何重复，因此此函数的复杂度为 O(满足条件 1 的 0 到 max_number 之间的数字数量)。要计算范围 a 到 b，我们只需要做ways(b) - ways(a - 1).
从 0 到 100 万计算这些数字需要不到 1 秒的时间，因为只有 42935 个数字满足结果。由于满足条件的数字很少，我们可以检查它们是否是其素数的倍数以满足条件 2。我将这部分留给读者，因为有多种方法可以做到这一点。
TL;DR：这通常被称为"带位掩码的数字动态规划">
用更熟悉的竞争性编程术语来说，您将计算dp[n_digit][mod_2357][is_less_than_r][digit_appeared][last_digit]= 具有n_digit位数字(包括前导零)的数字数，小于 R 的前n_digit位数字形成的数字，并且与其他属性匹配。用R和L-1做两次，然后取差额。所需的操作数约为 19(位数)* 210(mod)* 2 * 24(只需要检查个位数素数的外观)* 10 * 10，这显然是当今计算机可以管理的。
想想如何检查一个数字是否有效。
不是正常的方式。使用有限状态自动机，从左到右逐个数字获取输入。
为简单起见，假设输入具有固定位数(以便与 L/R 进行比较更容易。这是可能的，因为该数字最多具有与 R 一样多的数字)。
每个州都必须跟踪：
数字- 中出现了哪个数字(使用位掩码，有 4 个 1 位素数)
- 是范围 [L..R](前缀保证为真/假，否则前缀与 L/R 的前缀匹配)
- 前缀mod每个个位数素数的值是多少
- 最近的数字(用于检查所有连续数字对是否都是互质数)
构造有限状态自动机后，剩下的就简单了。只需使用动态规划来计算从起始状态到任何接受状态的路径数。
备注：此方法可用于计算可以使用有限状态自动机验证的任何类型的对象的数量(粗略地说，您可以使用具有恒定内存使用的程序检查属性是否满足，并按某种顺序逐个获取对象)
我们需要一个表，我们可以在其中查找与前缀匹配的后缀计数来构造有效数字。给定前缀的
right digit
prime combination
mod combination
和后缀长度，我们想要可搜索的后缀计数：
left digit
length
prime combination
mod combination
我开始用Python编码，然后切换到JavaScript能够提供一个片段。代码中的注释描述了每个查找表。其中有一些允许更快的枚举。有一些前缀-后缀计算示例来说明如何使用该表构建任意上限，尽管至少可以在制表期间进行一些前缀构造和聚合，也许所有前缀构造和聚合。
function gcd(a,b){
if (!b)
return a
else
return gcd(b, a % b)
}
// (Started writing in Python,
// then switched to JavaScript...
// 'xrange(4)' -> [0, 1, 2, 3]
// 'xrange(2, 4)' -> [2, 3]
function xrange(){
let l = 0
let r = arguments[1] || arguments[0]
if (arguments.length > 1)
l = arguments[0]
return new Array(r - l).fill(0).map((_, i) => i + l)
}
// A lookup table and its reverse,
// mapping each of the 210 mod combinations,
// [n % 2, n % 3, n % 5, n % 7], to a key
// from 0 to 209.
// 'mod_combs[0]' -> [0, 0, 0, 0]
// 'mod_combs[209]' -> [1, 2, 4, 6]
// 'mod_keys[[0,0,0,0]]' -> 0
// 'mod_keys[[1,2,4,6]]' -> 209
let mod_combs = {}
let mod_keys = {}
let mod_key_count = 0
for (let m2 of xrange(2)){
for (let m3 of xrange(3)){
for (let m5 of xrange(5)){
for (let m7 of xrange(7)){
mod_keys[[m2, m3, m5, m7]] = mod_key_count
mod_combs[mod_key_count] = [m2, m3, m5, m7]
mod_key_count += 1
}
}
}
}
// The main lookup table built using the
// dynamic program
// [mod_key 210][l_digit 10][suffix length 20][prime_comb 16]
let table = new Array(210)
for (let mk of xrange(210)){
table[mk] = new Array(10)
for (let l_digit of xrange(10)){
table[mk][l_digit] = new Array(20)
for (let sl of xrange(20)){
table[mk][l_digit][sl] = new Array(16).fill(0)
}
}
}
// We build prime combinations from 0 (no primes) to
// 15 (all four primes), using a bitmask of up to four bits.
let prime_set = [0, 0, 1<<0, 1<<1, 0, 1<<2, 0, 1<<3, 0, 0]
// The possible digits that could
// follow a digit
function get_valid_digits(digit){
if (digit == 0)
return [0, 2, 3, 4, 5, 6, 7, 8, 9]
else if ([2, 4, 8].includes(digit))
return [0, 2, 4, 6, 8]
else if ([3, 9].includes(digit))
return [0, 3, 6, 9]
else if (digit == 6)
return [0, 2, 3, 4, 6, 8, 9]
else if (digit == 5)
return [0, 5]
else if (digit == 7)
return [0, 7]
}
// Build the table bottom-up
// Single digits
for (let i of xrange(10)){
let mod_key = mod_keys[[i % 2, i % 3, i % 5, i % 7]]
let length = 1
let l_digit = i
let prime_comb = prime_set[i]
table[mod_key][l_digit][length][prime_comb] = 1
}
// Everything else
// For demonstration, we just table up to 6 digits
// since either JavaScript, this program, or both seem
// to be too slow for a full demo.
for (let length of xrange(2, 6)){
// We're appending a new left digit
for (let new_l_digit of xrange(0, 10)){
// The digit 1 is never valid
if (new_l_digit == 1)
continue
// The possible digits that could
// be to the right of our new left digit
let ds = get_valid_digits(new_l_digit)
// For each possible digit to the right
// of our new left digit, iterate over all
// the combinations of primes and remainder combinations.
// The ones that are populated are valid paths, the
// sum of which can be aggregated for each resulting
// new combination of primes and remainders.
for (let l_digit of ds){
for (let p_comb of xrange(16)){
for (let m_key of xrange(210)){
new_prime_comb = prime_set[new_l_digit] | p_comb
// suffix's remainder combination
let [m2, m3, m5, m7] = mod_combs[m_key]
// new remainder combination
let m = Math.pow(10, length - 1) * new_l_digit
let new_mod_key = mod_keys[[(m + m2) % 2, (m + m3) % 3, (m + m5) % 5, (m + m7) % 7]]
// Aggregate any populated entries into the new
// table entry
table[new_mod_key][new_l_digit][length][new_prime_comb] += table[m_key][l_digit][length - 1][p_comb]
}
}
}
}
}
// If we need only a subset of the mods set to
// zero, we need to check all instances where
// this subset is zero. For example,
// for the prime combination, [2, 3], we need to
// check all mod combinations where the first two
// are zero since we don't care about the remainders
// for 5 and 7: [0,0,0,0], [0,0,0,1],... [0,0,4,6]
// Return all needed combinations given some
// predetermined, indexed remainders.
function prime_comb_to_mod_keys(remainders){
let mod_map = [2, 3, 5, 7]
let mods = []
for (let i of xrange(4))
mods.push(!remainders.hasOwnProperty(i) ? mod_map[i] - 1 : 0)
function f(ms, i){
if (i == ms.length){
for (let idx in remainders)
ms[idx] = remainders[idx]
return [mod_keys[ms]]
}
let result = []
for (let m=ms[i] - 1; m>=0; m--){
let _ms = ms.slice()
_ms[i] = m
result = result.concat(f(_ms, i + 1))
}
return result.concat(f(ms, i + 1))
}
return f(mods, 0)
}
function get_matching_mods(prefix, len_suffix, prime_comb){
let ps = [2, 3, 5, 7]
let actual_prefix = Math.pow(10, len_suffix) * prefix
let remainders = {}
for (let i in xrange(4)){
if (prime_comb & (1 << i))
remainders[i] = (ps[i] - (actual_prefix % ps[i])) % ps[i]
}
return prime_comb_to_mod_keys(remainders)
}
// A brute-force function to check the
// table is working. Returns a list of
// valid numbers of 'length' digits
// given a prefix.
function confirm(prefix, length){
let result = [0, []]
let ps = [0, 0, 2, 3, 0, 5, 0, 7, 0, 0]
let p_len = String(prefix).length
function check(suffix){
let num = Math.pow(10, length - p_len) * prefix + suffix
let temp = num
prev = 0
while (temp){
let d = temp % 10
if (d == 1 || gcd(prev, d) == 1 || (ps[d] && num % d))
return [0, []]
prev = d
temp = ~~(temp / 10)
}
return [1, [num]]
}
for (suffix of xrange(Math.pow(10, length - p_len))){
let [a, b] = check(suffix)
result[0] += a
result[1] = result[1].concat(b)
}
return result
}
function get_prime_comb(prefix){
let prime_comb = 0
while (prefix){
let d = prefix % 10
prime_comb |= prime_set[d]
prefix = ~~(prefix / 10)
}
return prime_comb
}
// A function to test the table
// against the brute-force method.
// To match a prefix with the number
// of valid suffixes of a chosen length
// in the table, we want to aggregate all
// prime combinations for all valid digits,
// where the remainders for each combined
// prime combination (prefix with suffix)
// sum to zero (with the appropriate mod).
function test(prefix, length, show=false){
let r_digit = prefix % 10
let len_suffix = length - String(prefix).length
let prefix_prime_comb = get_prime_comb(prefix)
let ds = get_valid_digits(r_digit)
let count = 0
for (let l_digit of ds){
for (let prime_comb of xrange(16)){
for (let i of get_matching_mods(prefix, len_suffix, prefix_prime_comb | prime_comb)){
let v = table[i][l_digit][len_suffix][prime_comb]
count += v
}
}
}
let c = confirm(prefix, length)
return `${ count }, ${ c[0] }${ show ? ': ' + c[1] : '' }`
}
// Arbitrary prefixes
for (let length of [3, 4]){
for (let prefix of [2, 30]){
console.log(`prefix, length: ${ prefix }, ${ length }`)
console.log(`tabled, brute-force: ${ test(prefix, length, true) }nn`)
}
}
let length = 6
for (let l_digit=2; l_digit<10; l_digit++){
console.log(`prefix, length: ${ l_digit }, ${ length }`)
console.log(`tabled, brute-force: ${ test(l_digit, length) }nn`)
}