แนวคิด
เมื่อได้รับตัวเลขสองจำนวน P และ Q (P และ Q สามารถสูงสุดถึง 10^6) ซึ่งสร้างตัวเลข N = (P!/Q!) งานของเราคือลด N ให้เหลือ 1 โดยทำการดำเนินการมากที่สุดเท่าที่จะเป็นไปได้ จำไว้ว่าในแต่ละการดำเนินการ สามารถแทนที่ N ด้วย N/X ได้ถ้า N หารด้วย X ลงตัว หาจำนวนการดำเนินการสูงสุดที่เป็นไปได้
อินพุต
A = 7, B = 4
เอาต์พุต
4
คำอธิบาย
N คือ 210 และตัวหารคือ 2, 3, 5, 7
อินพุต
A = 3, B = 1
เอาต์พุต
2
คำอธิบาย
N คือ 6 และตัวหารคือ 2,3
วิธีการ
สังเกตได้ว่า การแยกตัวประกอบของตัวเลข P!/Q! นี้เหมือนกับการแยกตัวประกอบของตัวเลข (Q + 1)*(Q + 2)*…*(P – 1)*P
ควรสังเกตอีกว่า จำนวนการดำเนินการจะสูงสุดถ้าเราหาร N ด้วยเฉพาะตัวประกอบเฉพาะเท่านั้น ดังนั้นในทางกลับกัน เราต้องหาจำนวนตัวประกอบเฉพาะของ N ซึ่งรวมถึงตัวซ้ำด้วย
สมมติให้นับจำนวนตัวประกอบเฉพาะในการแยกตัวประกอบของทุกตัวเลขจาก 2 ถึง 1000000
ก่อนอื่น ใช้ Sieve of Eratosthenes เพื่อหาตัวหารเฉพาะของแต่ละตัวเลขเหล่านี้ อธิบายดังนี้ −
สร้างรายการจำนวนเต็มติดต่อกันจาก 2 ถึง N: (2, 3, 4, …, N)
สมมติ p เท่ากับ 2, ตัวเลขเฉพาะตัวแรก
เริ่มจาก p^2 นับขึ้นทีละ p และระบุตัวเลขแต่ละตัวที่มากกว่าหรือเท่ากับ p^2 เองในรายการ ดังนั้นตัวเลขเหล่านี้อาจเป็น p(p+1), p(p+2), p(p+3), ฯลฯ
หาตัวเลขแรกที่มากกว่า p ในรายการที่ไม่ได้ถูกระบุ พบว่า หากไม่มีตัวเลขดังกล่าว ให้หยุด มิฉะนั้น ให้สมมติ p เท่ากับตัวเลขนี้ (ซึ่งบ่งบอกถึงจำนวนเฉพาะถัดไป) และทำซ้ำจากขั้นตอน 3 อีกครั้ง
หลังจากใช้วิธี Sieve of Eratosthenes เราสามารถคำนวณจำนวนตัวประกอบเฉพาะในการแยกตัวประกอบของตัวเลขได้โดยใช้สูตรต่อไปนี้ −
primefactors[num] = primefactors[num / primedivisor[num]] + 1 ปัจจุบันสามารถใช้ prefix sum array สำหรับตัวประกอบเฉพาะและตอบสำหรับผลรวมบนช่วง [P, Q]
ตัวอย่างโค้ด
// โปรแกรม CPP เพื่อหาจำนวนการเคลื่อนที่สูงสุด // ที่เป็นไปได้ #include <bits/stdc++.h> using namespace std; #define N 1000005 // ใช้เก็บจำนวนตัวประกอบเฉพาะของแต่ละตัวเลข int primeFactors1[N]; // ฟังก์ชันแสดงการหาจำนวนตัวประกอบเฉพาะของแต่ละตัวเลข void findPrimeFactors(){ for (int a = 2; a < N; a++) // ตอนนี้ถ้า a เป็นจำนวนเฉพาะ if (primeFactors1[a] == 0) for (int b = a; b < N; b += a) // ตอนนี้เพิ่มค่าขึ้นหนึ่งจาก // จำนวนคูณก่อนหน้าของมัน primeFactors1[b] = primeFactors1[b / a] + 1; // สร้าง prefix sum // นี่จะช่วยได้สำหรับ // หลาย test cases for (int a = 1; a < N; a++) primeFactors1[a] += primeFactors1[a - 1]; } // โค้ดหลัก int main(){ // สร้าง primeFactors1 array findPrimeFactors(); int P = 7, Q = 4; // คำตอบที่ต้องการ cout << primeFactors1[P] - primeFactors1[Q]; return 0; }เอาต์พุต
4
