分数の話

Equations

整数Nが与えられる。
(1/x) + (1/y) = 1/N!
を満たす正数(x, y)の組の数(mod 1000007)を求めよ。

1000000!なので数え上げ系は無理。
変形すると
(x + y)*N! = xy
なのでこの式と組み合わせを上手く使って解くのかと思ったけどどうも上手くいかない。
相加・相乗平均とかも使ったけど駄目っぽい。

研究室の人に相談してみたところ、見事に解いてくれました。

(1/x) + (1/y) = (1/m)
を考える。
x, y > mを満たすので、x = m + a, y = m + bと置ける(a, b >= 1)。
これを代入して変形するとm^2 = abが得られる。

よって、(N!)^2を素因数分解してa, bに当てはめる方法の数を数えればOK。
ある素因数f[i]がc個あるとき、a, bに割り当てる方法はc+1通りある。
全ての素因数について、(素因数の数+1)を掛けていけば答えが出る。

ただ、結構制限時間が厳しいので高速化しないといけない。普通にやったらTLEしたので、素因数の数え上げの部分で「今見ている数字(変数e)が素数なら即終了」の処理を加えたら通った。

#include <iostream>
#include <cstdio>
//#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
//#include <limits>
#include <sstream>
//#include <functional>
using namespace std;

#define len(array)  (sizeof (array) / sizeof *(array))
#define rep(i, s, e) for(int i = s;i < e;i++)
#define rrep(i, e, s) for(int i = e;s <= i;i--)
#define vrange(v) v.begin(), v.end()
#define vrrange(v) v.rbegin(), v.rend()
#define vsort(v) sort(vrange(v))
#define vrsort(v) sort(vrrange(v))
#define arange(a) a, a + len(a)
#define asort(a) sort(arange(a))
#define arsort(a, t) sort(arange(a), greater<t>())
#define afill(a, v) fill(arange(a), v)
#define afill2(a, v, t) fill((t *)a, (t *)(a + len(a)), v)
#define fmax(a, b) (a < b? b : a)
#define fmin(a, b) (a > b? b : a)
#define fabs(a) (a < 0? -a : a)
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int INF = (int)1e9;
const int MOD = 1000007;
const double EPS = 1e-10;
//const int dx[] = {1, -1, 0, 0, 1, -1, -1, 1};
//const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
//const int weight[] = {0,1,10,100,1000,10000,100000,1000000,10000000};
//priority_queue<int, vector<int>, greater<int>> q;
typedef struct _Node {
  _Node(int arg1 = 0, int arg2 = 0 , int arg3 = 0) {
	i = arg1;
	j = arg2;
	k = arg3;
  }
  int i,j,k;
  bool operator <(const struct _Node &e) const{
    return i == e.i? j < e.j : i < e.i;
  }
  bool operator >(const struct _Node &e) const{
    return i == e.i? j > e.j : i > e.i;
  }
}node;

void doIt(){
  const int MAX_N = 1000002;
  bool bPrimes[MAX_N];
  vector<int> primes;
  int cnt[MAX_N];
  afill(bPrimes, true);
  afill(cnt, 0);
  bPrimes[0] = bPrimes[1] = false;
  primes.push_back(2);
  for(int i = 3; i < MAX_N; i += 2){
	if(bPrimes[i]){
	  primes.push_back(i);
	  for(int j = 3*i; j < MAX_N; j += 2*i) bPrimes[j] = false;
	}
  }
  //cout << primes.size() << endl;
  int n;
  ll ans = 1;
  cin >> n;
  rep(i, 2, n+1){
	int e = i;
	rep(j, 0, primes.size()){
	  while(e % primes[j] == 0){
		cnt[primes[j]]+=2;
		e /= primes[j];
	  }
	  if(bPrimes[e]){
		cnt[e] += 2;
	   	break;
	  }
	  // if(primes[j] > sqrt(e)) break;
	  if(primes[j] > e) break;
	}
  }
  rep(j, 0, primes.size()){
	ans = (ans * (cnt[primes[j]] + 1)) % MOD;
  }
  cout << ans << endl;
}

int main() {
  doIt();
  return 0;
}

確か一橋大学の入試問題で

(1/x) + (1/y) + (1/z) = 1/5
を満たすx, y, zの組を求めよ。

みたいな問題があったけど、あれみたいに考えればよかったみたい。