단순 검색
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 510
Accepted: 172
Description
John has recently arrived in Bucharest for the South Eastern European Regional Contest. John is famous for his theory of lucky numbers. That’s why all the contestants and spectators are very happy.
According to that theory 4 and 7 are lucky digits, and all the other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation. A very lucky number is a number that can be expressed as a product of several lucky numbers. A lucky number by itself is considered to be very lucky. For example, numbers 47, 49, 112 are very lucky.
Your task is to calculate the number of very lucky numbers that are not less than A and not greater than B. Of course, numbers A and B are given by John.
Input
The first line of the input contains a single integer T – a number of test cases. Each of the next T lines contains two integers separated by a single space – A and B.
Output
Output must contain T lines – answers for the test cases.
Sample Input
4
1 2
88 99
112 112
1 100
Sample Output
0
0
1
10
Hint
Constrains:
1 ≤ T ≤ 7777,
1 ≤ A ≤ B ≤ 1000000000000 (10
12).
#include
#include
#include
using namespace std;
const __int64 inf=1000000000000LL;
const int maxn=10002;
const int maxm=50000000;
int t,l,ll;
__int64 d[maxn],s[maxm],a,b;
void dfs(__int64 p,int step)
{
if(step>12) return;
d[l++]=p*10+4;
d[l++]=p*10+7;
dfs(p*10+4,step+1);
dfs(p*10+7,step+1);
}
void dfs1(__int64 p,int step)
{
if(step>=l)return;
if(d[step]>inf/p) return;
dfs1(p,step+1);
while(d[step]<=inf/p)
{
p*=d[step];
s[ll++]=p;
dfs1(p,step+1);
}
}
int main()
{
l=0,s[ll=1]=0;
dfs(0,1);
sort(d,d+l);
dfs1(1,0);
sort(s,s+ll);
int len=unique(s,s+ll)-s;
// cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
「저것과 비슷한 툴」을 조사하려면 어떻게 하면 좋을까?이 기사는 의 개발 팀 「 」에서 실시하고 있는 아웃풋 기획이다 요 전날, 어느 툴과 비슷한 툴을 씻어내려고, 생각대로 암운으로 검색하고 있었습니다만, 「아니, 비슷한 툴을 찾는 방법을 찾는 것이 좋지 않을까...?...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.