Đếm số đường đi trong bài mọi con đường về không

Submit solution
Points: 3 (partial)
Time limit: 1.0s
Python 3 3.0s
Memory limit: 977M
Python 3 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Số nguyên dương n nếu phân tích thành tích hai số tự nhiên \(a * b (a<=b)\) thì nó sẽ sinh ra số tự nhiên \(m=(a-1)*(b+1)\) cứ tiếp tục như vậy nếu \(m > 0\) nó tiếp tục sinh ra số tiếp theo. Bài toán đặt ra cho số n nguyên dương nó sẽ sinh ra các con và các con lại tiếp tục sinh ra các cháu ... cứ như vậy tới khi sinh ra tới các số \(0\) thì sẽ tạo thành một cây.

Ví dụ \(m= 12\) ta có cây được sinh ra như sau

enter image description here

Toto muốn biết là từ một số nguyên dương n thì có bao nhiêu con đường đi đến các số \(0\)

Input:

Dòng đầu tiên là số bộ kiểm thử \(t (1 \le t \le 100)\)

Các dòng tiếp theo gồm \(t\) dòng mỗi dòng chứa một số tự nhiên n \((1 \le n \le 10^5)\)

Output:

Gòm \(t\) dòng lần lượt tương ứng là kết quả đối với từng giá trị đầu vào, do các giá trị có thể rất lớn chỉ lấy kết quả là phần dư khi chia cho \(1000000007 (10^9+7)\)

Ví dụ

Input

2
12
1000

Output

6
140846736
tichpx

Comments


  • 0
    LINHCNTTVA1  commented on Feb. 22, 2022, 3:34 a.m. ← edited 
    #include<bits/stdc++.h>
using namespace std;
long long M=1e9+7;
//dung map de nho(dau vao-dau ra)
map<int, long long> Dic;
long long zero(int n)
{
    // n= a*b >> (a<b) a*a 
    // m=(a-1)(b+1)=ab-(b-a-1)<=n-1 
    //b-a-1>=1
    if(Dic.find(n)!= Dic.end()) return Dic[n];
    if(n==0) return Dic[n]=1;
    long long s=0;
    for(int a=1; a*a<=n;a++) //ptich n
    if(n%a==0) s=(s+zero((a-1)*(n/a+1)))%M;
    return Dic[n]=s;

}
int main()
{
    int test,n;
    cin>>test;
    while(test--){
        cin>>n;
        cout<<zero(n)<<"\n";
    }