寻找i*j=m的个数

问题描述

3*3的矩阵内容。

1 2 3

2 4 6

3 6 9

即a[i][j](1<=i<=n,1<=j<=n)=i*j。

问一个这样n*n的矩阵里面，里面m出现的次数。

例如n为3,m为6.

那么出现的次数就是2

Input

输入正整数N，表示N例测试（N<=20）。接着输入n（n<=10^5），m（<=10^9）。

Output

对每组输入数据，输出m出现的次数。

Sample Input

3 6

3 3

Sample Output

#include <iostream>

#define N 100000

using namespace std;

int main()

{

    int t;

    cin >> t;

    while(t--){

        int n;

        cin >> n;

        int m;

        cin >> m;

        int cnt=;

        for(int i=;i<=n;i++){

            if(m%i== && m/i<=n)

                cnt++;

        }

        cout << cnt << endl;

    }

    return ;

}

P.S.很多人把这个题想的太复杂。如果矩阵的每个数都要看，时间复杂度是10^10*2*10，肯定会超时。

我们仔细想下这个题目，每行最多只有一个数。如果第i行。如果能找到i*j==m并且j<=n，那么就可以。

每行判断m%i是否为0，m/i就是j如果<=n，那么那个数就是m。cnt++。

巴特西

寻找i*j=m的个数

最新文章

热门文章