fork(3) download
copy 
  1. uses math;
  2. const fi = '';
  3.       fo = '';
  4. var l, r, p, q, m, n, ans: int64;
  5.     f: array [0..100, 0..100] of int64;
  6.     ep, eq: array [0..100] of int64;
  7.  
  8. function pow(x, n: int64): int64;
  9. var i: longint;
  10.     res: int64;
  11. begin
  12.  res:=1;
  13.  for i:=1 to n do res:=res*x;
  14.  exit(res);
  15. end;
  16.  
  17. function GCD(a, b: int64): int64;
  18. begin
  19.  if (b = 0) then exit(a);
  20.  exit(GCD(b, a mod b));
  21. end;
  22.  
  23. function LCM(a, b: int64): int64;
  24. begin
  25.  exit((a div GCD(a, b)) * b);
  26. end;
  27.  
  28. function CheckOverflow(m, n: int64): boolean;
  29. const e = 0.000001;
  30.       oo = round(1e18)+1;
  31. var tmp, tmpm, tmpn, tmpu, tmpr: double;
  32. begin
  33.  tmpm:=m; tmpn:=n; tmpu:=GCD(m, n);
  34.  tmp:=tmpm/tmpu*tmpn;
  35.  tmpr:=oo;
  36.  exit(tmp-e < tmpr);
  37. end;
  38.  
  39. procedure EndProg;
  40. begin
  41.  close(input); close(output);
  42.  halt;
  43. end;
  44.  
  45. procedure Enter;
  46. var i, j: longint;
  47. begin
  48.  readln(l, r, p, q);
  49.  m:=trunc(logn(p, r));
  50.  n:=trunc(logn(q, r));
  51.  
  52.  ep[0]:=1;
  53.  for i:=1 to m do ep[i]:=ep[i-1]*p;
  54.  eq[0]:=1;
  55.  for i:=1 to n do eq[i]:=eq[i-1]*q;
  56.  
  57.  for i:=0 to m do
  58.   for j:=0 to n do f[i, j]:=-1;
  59. end;
  60.  
  61. function Find(i, j: longint): int64;
  62. var res: int64;
  63.     u, v: longint;
  64. begin
  65.  if (f[i, j] <> -1) then exit(f[i, j]);
  66.  res:=r div LCM(ep[i], eq[j]) - (l-1) div LCM(ep[i], eq[j]);
  67.  for u:=i to m do
  68.   for v:=j to n do
  69.    if (u > i) or (v > j) then
  70.     begin
  71.      if CheckOverflow(ep[u], eq[v]) and (LCM(ep[u], eq[v]) <= r) then res:=max(0, res-Find(u, v))
  72.      else break;
  73.     end;
  74.  f[i, j]:=res;
  75.  exit(res);
  76. end;
  77.  
  78. procedure Work;
  79. var i, j: longint;
  80. begin
  81.  for i:=0 to m do
  82.   for j:=0 to i-1 do
  83.    begin
  84.     if CheckOverflow(ep[i], eq[j]) and (LCM(ep[i], eq[j]) <= r) then ans:=ans+Find(i, j)
  85.     else break;
  86.    end;
  87. end;
  88.  
  89. procedure Answer;
  90. begin
  91.  writeln(ans);
  92. end;
  93.  
  94. begin
  95.  assign(input, fi); reset(input);
  96.  assign(output, fo); rewrite(output);
  97.  
  98.  Enter;
  99.  Work;
  100.  Answer;
  101.  
  102.  close(input); close(output);
  103. end.
  104.  
  105.  
Success #stdin #stdout 0s 484KB
comments (?)
stdin
copy 
1 20 3 2
stdout
copy 
4
https://ideone.com/R1AgnQ
1st Hunger Game - A. Good Numbers
language:
Pascal (fpc 3.0.4)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!