CCPC2019年河南省赛——咕咕的计数题 II

淡淡的烟草味﹌ 2022-02-19 09:25 218阅读 0赞

#                                           咕咕的计数题 II #

### 题目链接： ###

[http://acm.zzuli.edu.cn/problem.php?id=2523][http_acm.zzuli.edu.cn_problem.php_id_2523]

### 题目描述 ###

咕咕最近在学习初等数论，并且对下取整函数产生了极大的兴趣。下取整函数是指一个函数，自变量为 一个实数，因变量为一个整数，这个整数恰好是小于或等于自变量的最大的整数，通常记做 ⌊x⌋。例如， ⌊2.5⌋ = 2,⌊2⌋ = 2,⌊−2.5⌋ = −3。  
 咕咕发现，给定一个 a，并不是所有的自然数 n 都存在一个正整数 i 使得 ⌊n/i⌋ = a。那么，如果给定 l,r，咕咕好奇在区间 \[l,r\] 中有多少个正整数能使这个等式有正整数解 i 呢？  
 那么，聪明的你，你能告诉咕咕吗？

### 输入 ###

第一行有一个整数 T(1 ≤ T ≤ 106)，表示数据组数。接下来有 T 行，每行有三个数 a,l,r(1 ≤ a ≤ 1018,1 ≤ l ≤ r ≤ 1018)，表示一组询问。

### 输出 ###

输出 T 行，对每组询问，输出一个整数表示答案。

### 样例输入 Copy ###

4
    5 7 10
    7 39 42
    1000 1000 1000
    27 100 1000

### 样例输出 Copy ###

1
    2
    1
    617

### 提示 ###

### 数据范围 ###

当 n = 39,a = 7 时，能找到 i = 5 使得 ⌊39 /5 ⌋ = 7。

### 题意描述： ###

找出区间\[l,r\]的中数字除以一个整数向下取整得到整数a的数字个数。

### 解题思路： ###

暴力找规律发现当数字大于等于a\*a时的所有数字都符合条件，直接加上，而a\*a前的数字每个小区间中符合的个数即为n/a，且从1到n中符合个数为一个等差数列。求\[l,r\]区间结果，用\[1,r\]区间结果减去\[1,l-1\]结果得到。注意当数字不足一个区间的个数不在等差数列中等差数列向前推一个小区间，另外再加上。

### 程序代码： ###

#include<stdio.h>
    #include<string.h>
    long long t,a,l,r;
    long long num(long long n)
    {
    	long long d,a1,ans=0;
    	if(n==0)
    		return 0;
    	d=n/a;
    	if(d>=a)
    	{
    		ans+=n-a*a+1;
    		n=a*a-1;
    	}
    	d=n/a;
    	if(n>=d*(a+1)-1)
    		ans+=(1+d)*d/2;
    	else
    	{
    		d--;
    		ans+=(1+d)*d/2;
    		ans+=n-(d+1)*a+1;
    	}
    	return ans;
    }
    int main()
    {
    	scanf("%lld",&t);
    	while(t--)
    	{
    		scanf("%lld%lld%lld",&a,&l,&r);
    		printf("%lld\n",num(r)-num(l-1));
    	}
    	return 0;
    }

[http_acm.zzuli.edu.cn_problem.php_id_2523]: http://acm.zzuli.edu.cn/problem.php?id=2523