Artifact 199b4b73c8055efff93b24ecce65eb4f4f7b9ee5
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
typedef long long LL;
LL gcd(LL a, LL b)
{
while(a)
swap(a, b%=a);
return b;
}
LL lcm(LL a, LL b)
{
return a/gcd(a,b)*b;
}
class TheAlmostLuckyNumbers { public:
void genLuck(vector<LL>& v)
{
// lucky numbers
vector<LL> u;
for(int d=1; d<=10; ++d)
genLuck(d, u);
// filtering
for(int i=0; i<u.size(); ++i)
{
for(int j=0; j<i; ++j)
if( u[i] % u[j] == 0 )
goto next;
v.push_back( u[i] );
next:;
}
sort(v.begin(), v.end());
}
void genLuck(int d, vector<LL>& v)
{
// d-digit lucky numbers
for(int b=0; b<(1<<d); ++b)
{
LL n = 0;
for(int i=0; i<d; ++i)
n = n*10 + (b&(1<<i) ? 4 : 7);
v.push_back(n);
}
}
long long count(long long a, long long b)
{
vector<LL> v;
genLuck(v);
static const int M = 16;
// inclusion-exclusion
LL cnt = 0;
{
for(int m=1; m<(1<<M); ++m)
{
int bc = 0;
LL n = 1;
for(int i=0; i<M; ++i)
if( m & (1<<i) )
++bc, n=lcm(n, v[i]);
cnt += (bc&1) ? (b/n-(a-1)/n) : -(b/n-(a-1)/n);
}
}
// sieve
vector<LL> aml; // almost lucky numbers
for(int i=M; i<v.size() && v[i]<=b; ++i)
{
LL u = v[i];
for(LL s=a%u?(a/u+1)*u:a; s<=b; s+=u)
{
for(int k=0; k<M; ++k)
if( s%v[k]==0 )
goto next;
aml.push_back(s);
next:;
}
if( aml.size() > 10000000 ) {
sort(aml.begin(), aml.end());
aml.erase(unique(aml.begin(), aml.end()), aml.end());
}
}
sort(aml.begin(), aml.end());
aml.erase(unique(aml.begin(), aml.end()), aml.end());
return cnt + aml.size();
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, TheAlmostLuckyNumbers().count(a, b));}
int main(){
CASE(0)
long long a = 1LL;
long long b = 10LL;
long long _ = 3LL;
END
CASE(1)
long long a = 14LL;
long long b = 14LL;
long long _ = 1LL;
END
CASE(2)
long long a = 1LL;
long long b = 100LL;
long long _ = 39LL;
END
CASE(3)
long long a = 1234LL;
long long b = 4321LL;
long long _ = 1178LL;
END
CASE(4)
long long a = 1LL;
long long b = 10000000000LL;
long long _ = -1LL;
END
CASE(5)
long long a = 10000000000LL;
long long b = 10000000000LL;
long long _ = -1LL;
END
}
// END CUT HERE