HDU 2588 GCD

Description

The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6. 

(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem: 

Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

Input

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.

Output

For each test case,output the answer on a single line.

Sample Input

3

1 1

10 2

10000 72

Sample Output

1

6

260

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define inone(x) scanf("%d", &x);
#define intwo(x,y) scanf("%d%d", &x, &y);
using namespace std;
typedef unsigned long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int T, n, m;

int phi(int x)
{
  int res = 1;
  for (int i = 2; i*i <= x; i++)
  {
    if (x % i) continue;
    res *= i - 1; x /= i;
    while (x%i == 0) res *= i, x /= i;
  }
  return res * max(x - 1, 1);
}

int main()
{
  inone(T);
  while (T--)
  {
    intwo(n, m);
    int ans = 0;
    for (int i = 1; i * i <= n; i++)
    {
      if (n % i) continue;
      if (i >= m) ans += phi(n / i);
      if (i*i == n) continue;
      if (n / i >= m) ans += phi(i);
    }
    printf("%d\n", ans);
  }
  return 0;
}