เราต้องหาจำนวนการเรียงสับเปลี่ยนของ 1 ถึง n ดังนั้นจำนวนเฉพาะจะอยู่ที่ดัชนีเฉพาะ คำตอบอาจมีขนาดใหญ่ ส่งคืนโมดูโลคำตอบ 10^9 + 7 ดังนั้นหาก n =5 ผลลัพธ์จะเป็น 12 ดังนั้นจะมีการเรียงสับเปลี่ยน 12 ครั้ง การเรียงสับเปลี่ยนที่เป็นไปได้อย่างหนึ่งคือ [1,2,5,4,3] การเรียงสับเปลี่ยนที่ไม่ถูกต้องหนึ่งครั้งคือ [5,2,3,4,1] เนื่องจาก 5 ถูกวางไว้ที่ดัชนี 1 ซึ่งไม่ใช่จำนวนเฉพาะ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดวิธีหนึ่งที่เรียกว่า getNum ดังนี้ −
- prime :=รายการของจำนวนเฉพาะทั้งหมดตั้งแต่ 2 ถึง 100
- ตั้งค่า i :=0
- ในขณะที่ i <ความยาวของรายการเฉพาะ
- ถ้าไพรม์[i]> n ให้คืนค่า i
- ผม :=ผม + 1
- ความยาวกลับของไพรม์
- ปัญหาจริงจะได้รับการแก้ไขดังนี้
- x :=getNum(n), p :=1, m :=10^9 + 7
- สำหรับ i :=x เหลือ 0
- p :=p * i
- p :=p mod m
- สำหรับ i :=n – x เหลือ 0
- p :=p * i
- p :=p mod m
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution(object): def getNum(self,n): primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] i = 0 while i < len(primes): if primes[i]>n: return i i+=1 return len(primes) def numPrimeArrangements(self, n): """ :type n: int :rtype: int """ x = self.getNum(n) p = 1 m = 1000000000+7 for i in range(x,0,-1): p*=i p%=m for i in range(n-x,0,-1): p*=i p%=m return p ob1 = Solution() print(ob1.numPrimeArrangements(100))
อินพุต
100
ผลลัพธ์
682289015
