列表

详情


NC251444. 简单的数学题

描述

小红最近沉迷于数学题,她现在想考考小明一道简单的数学题:
给定正整数 mx ,小红定义一个正整数 y 和 x 具有关于 m 的等价关系,则 y 满足:

使得对于正整数 k=1,2\ ...\ 10^{100},当 kx \leqslant m 时,ky \leqslant m。当 kx > m 时,ky > m 。

小红想知道有多少个正整数 yy 和 x 具有关于 m 的等价关系?

输入描述

输入共 T+1 行。

第一行一个整数表示 T \ (1≤T≤10^5)

接下来 T 行,每行 2 个正整数,m,\ x \ (1 ≤ x ≤ m ≤ 10^9) ,m,x如上描述。

输出描述

输出共 T 行,每行一个整数,表示多少个正整数 yx 具有关于 m 的等价关系。

示例1

输入:

3
15 7
12 12
6 1

输出:

2
6
1

说明:

第一问,m=15,x=7,显然y=x=7满足。
y=6时,对于k=1,2时kx≤m且ky≤m。k=3,4...10^{100}, kx>m且ky>m。
可以证明没有其他正整数y与x有关于m的等价关系。

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 51ms, 内存消耗: 1184K, 提交时间: 2023-05-05 21:49:10

#include<stdio.h>
int main()
{
    int T,m,x;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&m,&x);
        printf("%d\n", m/(m/x)-m/(m/x+1));
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 331ms, 内存消耗: 1284K, 提交时间: 2023-05-05 21:51:18

#include<iostream>
using namespace std;
int main()
{
	int t,m,x;
	cin>>t;
	while(t--)
	{
		cin>>m>>x;
		cout<<m/(m/x)-m/((m/x)+1)<<endl;
	}
}

pypy3 解法, 执行用时: 812ms, 内存消耗: 30984K, 提交时间: 2023-05-07 10:57:20

for _ in range(int(input())):
    m, x = map(int, input().split())
    
    k = m // x
    print(m // k - m // (k + 1))

Python3 解法, 执行用时: 1137ms, 内存消耗: 5420K, 提交时间: 2023-05-06 10:34:19

for _ in range(int(input())):
    m,x=map(int,input().split())
    print(m//(m//x)-m//(m//x+1))

上一题