結果

問題 No.847 Divisors of Power
ユーザー pengin_2000pengin_2000
提出日時 2019-07-05 23:02:48
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 1,337 bytes
コンパイル時間 545 ms
コンパイル使用メモリ 34,028 KB
実行使用メモリ 8,736 KB
最終ジャッジ日時 2024-04-16 08:00:00
合計ジャッジ時間 3,744 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
8,604 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます

ソースコード

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