首页 > 试题广场 >

取模方程

[编程题]取模方程
  • 热度指数:263 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个非负整数。求有多少个正整数,满足。如果有无穷个解输出"inf"。

输入描述:
一行两个数字



输出描述:
一行一个数字或字符串表示答案。
示例1

输入

7 3

输出

1

说明

7 \mod 4 = 3
示例2

输入

15 15

输出

inf
分为三种情况讨论
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)