#P10788. Perfect Positive Fractions

    ID: 12827 Type: Default 1000ms 256MiB

Perfect Positive Fractions

Perfect Positive Fractions

Two players, Y and C, are playing a fascinating game with rational numbers. A positive fraction is defined as a reduced fraction whose numerator and denominator are positive integers. A positive fraction x is called a perfect positive fraction if it belongs to the unique set S that satisfies the following properties:

  • \( \frac{1}{2} \in S \).
  • If \(\frac{1}{2} < x < 2\), then \(x \notin S\).
  • If \(x \in S\), then \(\frac{1}{x} \in S\).
  • If \(x \in S\), then \(x+2 \in S\).
  • If \(x \in S\) and \(x > 2\), then \(x-2 \in S\).

It can be shown that these five conditions uniquely determine the set S. Define a function \(f(i,j)\) for positive integers \(i,j\) as follows: if \(i\) and \(j\) are coprime and \(\frac{i}{j} \in S\) then \(f(i,j)=1\), and \(f(i,j)=0\) otherwise.

Given two positive integers n and m, your task is to compute the number of perfect positive fractions \(\frac{i}{j}\) with \(1 \le i \le n\) and \(1 \le j \le m\). In other words, calculate:

[ \sum_{i=1}^{n} ; \sum_{j=1}^{m} f(i,j). ]

Note: A fraction is considered in its reduced form (i.e. the numerator and denominator are coprime) when evaluating \(f(i,j)\).

inputFormat

The input consists of a single line containing two positive integers n and m (separated by a space).

outputFormat

Output a single integer representing the count of perfect positive fractions \(\frac{i}{j}\) with \(1 \le i \le n\) and \(1 \le j \le m\).

sample

2 3
2