取模方程

[编程题]取模方程

热度指数：267 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个非负整数 $\mathit a,b$ 。求有多少个正整数 $\mathit x$ ，满足 $a \mod x = b$ 。如果有无穷个解输出"inf"。

输入描述:

一行两个数字。

输出描述:

一行一个数字或字符串表示答案。

示例1

输入

7 3

输出

说明

示例2

输入

15 15

输出

inf

算法知识视频讲解

pein531

分为三种情况讨论

1) a<b：这种情况下方程根本不成立，无解

2) a=b：此时x对任意大于等于1的正整数都成立，有无穷多解

3) a>b：正常求解，先将余数b减去，diff=a-b，然后搜索可能的x，使得diff%x=0。x从1开始搜索，上界是diff开方并向上取整（因为当x大于这个数的时候，实际上和小于这个数的时候是对称的）。

from math import sqrt, ceil

a, b = map(int, input().strip().split())
if a < b:
    # a比b还小，肯定无解
    print(0)
elif a == b:
    # a=b有无穷多解
    print("inf")
else:
    # a>b正常求解
    diff = a - b      # 先将余数减去
    upper_bound = ceil(sqrt(diff))    # x的搜索上界
    res = 0
    # 遍历x的可能性
    for x in range(1, upper_bound + 1):
        if diff % x == 0:
            # 在可以整除x的情况下才计算次数
            if diff != x**2:
                # 当diff != x**2时，除数和商可以通过交换位置形成两个解
                # 但需要它们两个至少有一个大于b才能增加一种可能的解，如果除数和商都小于等于b，余数是不可能为b的
                if x > b:
                    res += 1
                if diff // x > b:
                    res += 1
            else:
                # 当diff = x**2时，除数和商相等，最多只能增加一个解，当且仅当它们大于b的时候取得
                if x > b:
                    res += 1
    print(res)

发表于 2021-01-22 10:09:38 回复(5)

励志要变胖的人

1. a<b 无解

2. a=b 无穷解

3. a>b 需要求解，首先要明确x的值要大于b，然后我们去求x的所有可能值，再除去小于等于b的值,即可求得答案。x的所有可能值可以通过求a-b的所有因子来获得，求因子的过程中，我们每次循环可以求到两个因子（可能会有相同因子），然后分别判断是否大于b即可。(本题测试用例较弱，没有考虑到相等因子也能过)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    int ans=0;
    if(a>b){
        int m=a-b;
        int t=sqrt(a-b);
        for(int i=1;i<=t;i++){
            if(m%i==0){
                int temp=m/i;
                if(i>b)
                    ans++;
                if(i!=temp&&temp>b)
                    ans++;
            }
        }
        cout<<ans;
    }
    else if(a==b)
        cout<<"inf";
    else
        cout<<0;
}

编辑于 2021-09-06 00:42:46 回复(0)