T51071 Tony到死都想不出の数学题

T51071 Tony到死都想不出の数学题

自己摘的题出了数据挂一下链接
(a, b) 均为整数

设 (M(a)) 为满足 ((a + b) | ab) 的 (b) 的个数， 求 (M(a))

(a <= 10^{9})

Solution

设有 (n(a + b) = ab)
则有 (an + bn - ab = 0)
两边加上 (a^{2}) 得 (an +bn - ab + a^{2} = a^{2})
因式分解得 ((a - n)(a + b) = a^{2})
观察此式， 发现 (0 < (a - n), (a +b) in Z)
故每对 (n^{2}) 的因子对应唯一一个 (b)
故答案为 (a^{2}) 的因数个数 - 1（减掉完全平方那个， 对应的 (b) 为 (0)）除以2， 即：$$frac{d_{0}(a^{2}) - 1}{2}$$

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cmath>
#define LL long long
#define REP(i, x, y) for(int i = (x);i <= (y);i++)
using namespace std;
int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
int a;
int get_numd(int x){
	int num = 0;
	REP(i, 1, x)
		if(x % i == 0)num++;
	return (num - 1);
	}
int main(){
	a = RD();
	printf("%d
", get_numd(a));
	return 0;
	}