結果

問題 No.3310 mod998
コンテスト
ユーザー pengin_2000
提出日時 2025-10-24 22:19:44
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,694 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 215 ms
コンパイル使用メモリ 40,136 KB
最終ジャッジ日時 2026-02-22 13:49:38
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
int a[1003], sum[1003];
char s[100005];
void solve()
{
	int n, m;
	scanf("%d %d", &n, &m);
	int i, j;
	a[0] = 1;
	sum[0] = 0;
	sum[1] = 1;
	int left, right;
	for (i = 1, left = -1; left < 0; i++)
	{
		a[i] = a[i - 1] * n % 998;
		sum[i + 1] = (sum[i] + a[i]) % 998;
		for (j = 0; j < i; j++)
		{
			if (a[j] == a[i])
			{
				left = j;
				right = i;
				break;
			}
		}
	}
	int res;
	int len, k;
	for (; m > 0; m--)
	{
		scanf("%s", s);
		for (len = 0; s[len] != '\0'; len++);
		if (len < 5)
		{
			k = 0;
			for (i = 0; i < len; i++)
				k = 10 * k + s[i] - '0';
			k++;
			if (k <= left)
				res = sum[k];
			else
				res = sum[left];
			k -= left;
			if (k > 0)
			{
				res += k / (right - left) % 998 * (sum[right] - sum[left] + 998) % 998;
				k %= right - left;
				res += sum[left + k] - sum[left] + 998;
				res %= 998;
			}
			printf("%d\n", res);
		}
		else
		{
			res = sum[left];
			j = left - 1;
			for (i = len - 1; j > 0; i--)
			{
				k = j / 10;
				j %= 10;
				if (s[i] - '0' >= j)
					s[i] -= j;
				else
				{
					k++;
					s[i] = s[i] + 10 - j;
				}
				j = k;
			}
			k = 0;
			for (i = 0; i < len; i++)
				k = (10 * k + s[i] - '0') % (right - left);
			res += sum[left + k] - sum[left] + 998;
			j = k;
			for (i = len - 1; j > 0; i--)
			{
				k = j / 10;
				j %= 10;
				if (s[i] - '0' >= j)
					s[i] -= j;
				else
				{
					k++;
					s[i] = s[i] + 10 - j;
				}
				j = k;
			}
			k = 0;
			for (i = 0; i < len; i++)
				k = (10 * k + s[i] - '0') % 998;
			res += k * (sum[right] - sum[left] + 998);
			res %= 998;
			printf("%d\n", res);
		}
	}
	return;
}
int main()
{
	int t;
	scanf("%d", &t);
	for (; t > 0; t--)
		solve();
	return 0;
}
0