HSG9 Phú Thọ 2026 - Đếm số cặp nghiệm

Điểm: 30,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Output Only, Pascal, PyPy, Python, ~~Scratch~~, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Cho số nguyên dương ~n~, hãy đếm số cặp nghiệm nguyên dương ~(x, y)~ của phương trình thỏa mãn: $$\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$$

Ký hiệu ~n! = 1 \times 2 \times 3 \times ... \times n~.

Yêu cầu: Hãy tính số lượng cặp nghiệm nguyên dương ~(x, y)~ thỏa mãn đề bài.

Input

Một dòng duy nhất chứa số nguyên dương ~n~ (~n \le 10^6~).

Output

Số cặp nghiệm nguyên dương ~(x, y)~ thỏa mãn đề bài chia dư cho ~20252026~.

Sample Input 1

Sample Output 1

Giải thích: Với ~n = 2~ ta có 3 cặp nghiệm thỏa mãn là: ~(3, 6); (4, 4); (6, 3)~.

Subtasks

Subtask 1 (50% số điểm): ~n \le 10~.
Subtask 2 (50% số điểm): Không có ràng buộc gì thêm.

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

tikl20tok đã bình luận lúc 28, Tháng 2, 2026, 14:06

Ban code tren duoc detect boi trang web nen co 1 so phan no ra khong duoc nhu mong muon, vi du phan cout o duoi. Xin cam on.

-1

tikl20tok đã bình luận lúc 28, Tháng 2, 2026, 14:05

dap an day nhe:

include<bits/stdc++.h>

using namespace std; bool a[(long long)1e6+10];

int main() {

ios::sync_with_stdio(false);
cin.tie(NULL);

long long n;
cin>>n;
memset(a,true,sizeof(a));
long long i,j,k;
//sang era
vector&lt;long long> snt;
snt.reserve((long long)1e6+5);
snt.push_back(0);
for (i=4;i<=(long long)1e6+1;i+=2)
{
    a[i]=false;
}
for (i=3;i*i<=1e6+1;i++)
{
    if (a[i]==true)
    {
        for (j=i*i;j<=1e6+1;j+=i)
        {
            a[j]=false;
        }
    }
}
long long demsnt=0;
for (i=2;i<=1e6+5;i++)
{
    if (a[i]==true)
    {
        demsnt+=1;
        snt.push_back(i);
    }
}
//end
long long tonguoc=1;
long long tong;
for (i=1;i<=demsnt;i++)//legendre algorythm
//tim hieu them o ai
{
    if (snt[i]<=n)
    {
        j=n;
        tong=0;
        while (j>0)
        {
            tong+=j/snt[i];
            j/=snt[i];
        }
        tonguoc=((tonguoc%20252026)*(2*(tong)%20252026+1))%20252026;//li do + 1 la co the khong chon so do, vd 1 den 4, ta co 2 so 2 nhung dong thoi ta cung co 1 cach khong chon la 1 (tuc 2^0)
    }
    else
    {
        break;
    }
}
cout<&lt;tonguoc;






return 0;

}