原文链接: https://leetcode-cn.com/problems/prime-arrangements

英文原文

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

 

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

Input: n = 100
Output: 682289015

 

Constraints:

• 1 <= n <= 100

中文题目

请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。

让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。

由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。

 

示例 1：

输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。

示例 2：

输入：n = 100
输出：682289015

 

提示：

• 1 <= n <= 100

通过代码

高赞题解

这题不难，但是对没有bigint的js有个不小的坑：
此题若是直接求出了：

1. 素数的全排列方式总数对于10**9+7的余数a
2. 非素数的全排列方式总数对于10**9+7的余数b
   若直接计算 (a*b)%(10**9+7)时由于数位溢出，导致计算结果不准确，此不准确结果为：682289019
   因此最终的a*b乘法应该将其中的一个数拆为两部分，分别相乘并取余：

js大数相乘并取余

let MOD = 10**9+7;
function multi(a,b){
    //将b拆成2部分
    let t=Math.floor(b/100000),
        t2=b % 100000
    let sum=0
    for(let i=0;i<t;i++){
      sum=(sum+100000*a) % MOD
    }
    sum=(sum+t2*a)%MOD
    return sum
}

最终代码为：

var numPrimeArrangements = function(n) {
    let MOD = 10**9 + 7;
    function A(n,m){
        return (m===0?1:A(n,m-1)*(n-m+1)) % MOD;
    }
    
    function su(a){
        if(a<2)return false;
        if(a===2)return true;
        for(let i=2;i<a;i++){
            if(a%i===0)return false;
        }
        return true;
    }
    
    function multi(a,b){
        //将b拆成2部分
        let t=Math.floor(b/100000),
            t2=b % 100000
        let sum=0
        for(let i=0;i<t;i++){
          sum=(sum+100000*a) % MOD
        }
        sum=(sum+t2*a)%MOD
        return sum
    }
    
    let numSu = 0;
    for(let i=1;i<=n;i++){
        if(su(i)){
            numSu++;
        }
    }
 
    let a = A(numSu,numSu);
    let b = A(n-numSu,n-numSu);
 
    return (a*b) % MOD;
};

统计信息

通过次数	提交次数	AC比率
7659	15573	49.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言