Advertisement
Guest User

Untitled

a guest
Jun 11th, 2014
313
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.03 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long llint;
  8.  
  9. const int MAXN = 9;
  10.  
  11. vector<int> v;
  12.  
  13. int A, B;
  14. int ans = 0;
  15.  
  16. inline void dodaj(int x, int k) {
  17. ans += k*(B/x);
  18. ans -= k*((A-1)/x);
  19. }
  20.  
  21. int gcd(int a, int b) {
  22. return !b ? a : gcd(b, a%b);
  23. }
  24.  
  25. void rec(int u, int x, int k) {
  26. if(x == (int)v.size()) return;
  27.  
  28. rec(u, x+1, k);
  29.  
  30. int g = gcd(u, v[x]);
  31. if(llint(u/g)*v[x] <= B) {
  32. dodaj((u/g)*v[x], -k);
  33. rec((u/g)*v[x], x+1, -k);
  34. }
  35. }
  36.  
  37. int main(void) {
  38. for(int i = 1; i <= MAXN; ++i)
  39. for(int j = 0; j < (1<<i); ++j) {
  40. llint x = 0;
  41. for(int k = 0; k < i; ++k)
  42. if(j&(1<<k)) x = x*10 + 5; else
  43. x = x*10 + 3;
  44. v.push_back(x);
  45. }
  46.  
  47. sort(v.begin(), v.end());
  48. for(int i = 0; i < (int)v.size(); ++i)
  49. for(int j = v.size()-1; j > i; --j)
  50. if(v[j]%v[i] == 0) {
  51. v.erase(v.begin()+j);
  52. }
  53.  
  54. scanf("%d %d", &A, &B);
  55. rec(1, 0, -1);
  56. printf("%d\n", ans);
  57. return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement