BestCoder Round #84 Dertouzos

Dertouzos

Accepts: 205 Submissions: 1040 Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) 問題描述

正整數$x$稱為$n$的positive proper divisor, 當且僅當$x | n$并且$1 \le x < n$. 例如, 1, 2, 和3是6的positive proper divisor, 但是6不是.

Peter給你兩個正整數$n$和$d$. 他想要知道有多少小于$n$的整數, 滿足他們的最大positive proper divisor恰好是$d$.      

輸入描述

輸入包含多組資料, 第一行包含一個整數$T$ $(1 \le T \le 10^6)$表示測試資料組數. 對于每組資料:

第一行包含兩個整數$n$和$d$ $(2 \le n, d \le 10^9)$.      

輸出描述

對于每組資料, 輸出一個整數.
      

輸入樣例

9
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
100 13      

輸出樣例

1
2
1
0
0
0
0
0
4
      

在BC上AC的第一道題
        
  
               
，題意很好了解，但是暴力解的話，容易逾時。      

#include<stdio.h>
int f(__int64 m)
{
	int i=2;
	while(m%i!=0)
	{
		i++;
	}

	return m/i;		 		
}             //找出一個數的<span style="font-family: Arial, Helvetica, sans-serif;">最大positive proper divisor</span>

int main()
{
	int t;
	__int64 n,d;
	scanf("%d",&t);
		while(t--)
		{
			__int64 sum=0;
			scanf("%I64d%I64d",&n,&d);
			for(__int64 i=2*d;i<n;)      //找規律
			{
				if(f(i)==d)
				 sum++;
				 i=i+d;			 	
			}
			printf("%I64d\n",sum);
		}
	return 0;
}