結果

問題 No.847 Divisors of Power
ユーザー pengin_2000
提出日時 2019-07-05 23:02:48
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,337 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 32,628 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-10-06 22:53:11
合計ジャッジ時間 4,082 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 4 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<math.h>
int main()
{
	long long int n, k, m;
	scanf("%lld %lld %lld", &n, &k, &m);
	if (n == 1)
	{
		printf("1\n");
		return 0;
	}
	long long int p[100005], count[100005];
	long long int i, l = 0, j;
	while (n > 1)
	{
		for (i = 2; i <= sqrt(n); i++)
			if (n % i == 0)
				break;
		if (n % i == 0)
		{
			p[l] = i;
			count[l] = 0;
			while (n % i == 0)
			{
				count[l]++;
				n /= i;
			}
			l++;
		}
		else
		{
			p[l] = n;
			count[l] = 1;
			l++;
			n /= n;
		}
	}
	for (i = 0; i < l; i++)
		if (p[i] > m)
			l = i;
	for (i = 0; i < l; i++)
		count[i] *= k;
	long long int ans = 0;
	long long int ii[100005], v[100005];
	for (i = 0; i < l; i++)
		ii[i] = 0;
	for (i = 0; i < l; i++)
		v[i] = 1;
	long long int now;
	for (;;)
	{
		now = 1;
		for (i = 0; i < l; i++)
		{
			now *= v[i];
			if (now > m)
				break;
		}
		if (i == l && now <= m)
		{
			ans++;
			ii[l - 1]++;
			v[l - 1] *= p[l - 1];
		}
		else
		{
			if (i == 0)
				break;
			for (; i < l; i++)
			{
				ii[i] = 0;
				v[i] = 1;
			}
			i -= 2;
			ii[i]++;
			v[i] *= p[i];
		}
		for (i = l - 1; i > 0; i--)
		{
			if (ii[i] > count[i])
			{
				for (j = i; j < l; j++)
				{
					ii[j] = 0;
					v[j] = 1;
				}
				ii[i - 1]++;
				v[i - 1] *= p[i - 1];
			}
		}
		if (ii[0] > count[0])
			break;
	}
	printf("%lld\n", ans);
	return 0;
}
0