Số X

Tác giả:

Small

Dạng bài

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Thấy Khoa rất thích học toán, một hôm thầy giáo đã ra một bài toán cho Khoa giải như sau:

Xác định hai hàm \(f,g\) trên các số nguyên dương như sau:

\(f(n)\) = tích các chữ số khác 0 của \(n\)
\(g(n)\) có trị trị là:
- \(n\) nếu n<10
- \(g(f(n))\) ngược lại
  Khoa cần xử lý \(Q\) truy vấn, trong mỗi truy vấn sẽ được cung cấp 3 số nguyên \(l,r,k\). Khoa cần in số lượng số nguyên \(x\) nằm giữa \(l\) và \(r\), trong đó \(g(x)=k\).

Input

Dòng đầu tiên chứa số nguyên \(Q\) \((1 \le Q \le 2 \times 10^5)\) đại diện cho số lượng truy vấn
\(Q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(l,r,k (1 \le l \le r \le 10^6,1 \le k \le9)\)

Output

Với mỗi truy vấn, in ra một dòng chứa câu trả lời cho truy vấn đó.

Example

Test 1

Input

Output

Note

Có 1 số \(x\) để \(g(x)\)=9 đó là \(g(33)\)=9 với \(g(33)\)=\(g(3\times3)\)=\(g(9)\)=9
Có 4 số \(x\) để \(g(x)\)=6 là: \(g(47)\)=\(g(48)\)=\(g(60)\)=\(g(61)\)=6
Không có số \(x\) nào trong khoảng 47 đến 55 để \(g(x)\)=7.
Có 8 số \(x\) để \(g(x)\)=4 là: \(g(4)\)=\(g(14)\)=\(g(22)\)=\(g(27)\)=\(g(39)\)=\(g(40)\)=\(g(41)\)=\(g(58)\)=4

Bình luận

C++

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int F[10][1000001]={};
int f(int n)
{
    int d=1;
    while (n>0)
    {
        if (n%10!=0) d=d*(n%10);
        n=n/10;
    }
    return d;
}
int g(int n)
{
    if (n<10) return n; else return g(f(n));
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,i,x,j,l,r;
    for(i=1;i<=1000000;i++)
    {
        x=g(i); F[x][i]=F[x][i-1]+1;
        for(j=1;j<=9;j++) {if (j!=x) F[j][i]=F[j][i-1];}
    }
    cin>>n; while (n--)
    {
        cin>>l>>r>>x; cout<<F[x][r]-F[x][l-1]<<endl;
    }
    return 0;
}

-6

rukashii 9:34 p.m. 30 Tháng 12, 2021

bài hay 😊

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

1 phản hồi