ex.dpr

来自「tongji acm-online judge solution」· DPR 代码 · 共 107 行

{
AC in 0.046 sec
"test.dpr" is the simple program(stupid program).

Write a simple program which precomputes values for all n (it may be a long time) 
, writes to file the values for each n=10^5*K where K is a non-negative integer
and create an array of constants where i-th value is f(i*10^5).

Then the program gets n and finds k s.t. k*10^5<=n<(k+1)*10^5 and calulates values f(k*10^5+1) to f(n) with O(10^5).
}
program Ural_1309(Input,Output);
const
	MaxN=100000000;
	Interval=100000;
	Divisor=9973;
	LeadResult:array[0..MaxN div Interval]of Longint=
	(0,2592,6706,4944,714,464,6707,3198,8950,9345,5392,306,7174,4396,4775,7358,4541,5504,5452,806,1890,8598,
	8016,1375,8162,7227,7999,1431,3340,3420,84,2025,821,3385,6114,1887,8138,4412,2362,9216,6520,5312,3096,
	4598,963,202,3301,4243,3266,3921,3149,8815,4310,9494,965,2364,1002,2205,4208,9780,2416,7663,2301,5925,
	6194,8833,2839,2010,6724,2030,2835,3684,1595,6975,136,665,2775,7310,7989,8706,80,8417,2468,8074,5070,
	6808,7684,224,2387,5900,8614,2518,6927,5951,2475,7112,8674,917,6741,8169,742,8348,8025,7350,8125,1950,
	1286,7217,7686,6310,7696,1714,5134,7400,1336,6133,5994,6478,3307,5269,6823,6940,9590,5651,8390,792,
	2801,7081,450,6717,9492,7208,1710,8748,6638,9220,5196,6663,4979,4808,7710,5227,3977,8090,5146,9652,
	6696,7454,9166,1981,9444,2302,3346,4560,594,3857,5529,4974,852,850,510,8850,6145,940,9731,4083,9800,
	1574,2722,341,118,3992,6221,986,2148,665,9718,745,3155,3235,6522,3189,719,3959,5070,6630,4838,4796,
	8670,837,3213,6880,2630,9915,5885,9054,9257,8465,2124,7615,4499,7471,9063,2425,910,3172,1524,9425,8367,
	7663,6178,2461,7757,7941,4597,3080,9137,4452,7840,1040,4565,9491,4310,5112,3173,6188,1395,9111,2102,
	5149,763,743,4368,4465,6561,1758,6298,6939,6663,5832,1071,8347,839,9738,8184,956,6976,5612,7681,7957,
	8875,2203,34,952,7422,8130,6875,3823,6949,5585,2688,4409,9393,9090,8578,8935,4288,4859,6799,8340,9145,
	9787,4302,1426,75,5778,6482,2124,444,3148,1211,9298,4033,1024,5328,7821,692,656,2106,8535,9480,9558,
	4684,2555,3710,1263,6944,6181,8391,4778,4056,960,2392,1313,5152,601,7491,1584,2702,2897,1817,7406,9010,
	5569,3983,2400,9407,7338,9444,7298,8661,2452,7461,6181,4348,8907,1803,8285,7089,2641,5467,2562,9457,
	5296,1497,8542,4137,8556,3188,1860,3358,7315,5399,7301,8896,1412,2470,3535,4299,5425,2892,8046,7876,
	8131,878,650,2636,2964,6294,3055,2205,7465,5250,4756,8655,1346,8436,1406,7792,1468,8691,8586,1657,703,
	7120,3258,8250,7130,5454,3529,1963,4628,5053,4773,6769,8720,367,5675,9831,6121,2386,2082,9040,6706,
	2447,1098,9586,3322,9685,8197,8401,1272,6142,4544,4546,3757,7743,2532,5314,3531,1047,7396,3706,4800,
	5912,9097,3413,7240,7911,2743,3691,9512,6193,842,2353,731,892,4442,1018,765,6824,1281,4389,8704,4663,
	3113,8571,3868,9608,5400,825,7325,4939,4790,4183,5665,4615,2928,5484,5777,7728,7423,2958,1440,3639,
	8542,8205,6763,7579,6277,6797,4519,3829,5933,1510,1210,8345,5377,3634,9146,1720,2482,6514,9536,9688,
	5693,7838,9256,9723,369,8194,211,632,9299,241,1924,8229,4887,7415,3407,9901,9433,9263,7485,6834,9806,
	5424,3282,4434,2868,2823,9758,7360,7503,6606,2977,1846,2227,4083,2555,1952,8573,7011,2813,2067,5950,
	9012,8061,2376,5350,9344,1672,2365,3202,8491,2263,4690,2349,3852,95,5022,641,8211,6431,3528,7788,3295,
	1605,8902,6607,1421,2282,9748,6034,8409,9611,4967,7829,1393,9420,6116,4334,3577,8459,6003,7005,1411,
	2137,6550,4711,4511,1844,1986,5978,7172,7657,8802,2125,8589,3810,1289,6459,760,1332,2281,2038,4155,491,
	3552,5711,2133,9510,8083,4514,6239,2678,6568,8055,5765,889,7494,7323,4619,3252,6078,3861,2229,2428,
	7071,8087,7298,8901,4282,4239,1157,7050,7919,7367,2143,8602,5012,1400,2226,8837,506,889,2827,590,2845,
	7154,9638,6641,9101,9100,9400,559,253,4696,8237,8138,8753,5544,9818,8779,3294,3937,5329,1017,577,2100,
	5968,4061,7789,1611,8386,1206,5344,4730,8141,1194,4029,2752,692,774,9494,6558,796,2898,1145,5237,4804,
	2854,1948,4432,6012,5853,1984,6815,8298,251,9556,227,8366,71,7890,3645,218,333,71,6082,924,4371,677,
	8870,2058,5140,5948,5296,4521,7653,1497,8844,7797,2094,1976,9448,7575,4760,5517,2136,5886,4597,5170,
	3481,2136,3311,8620,4926,7018,423,6078,7070,2785,6933,627,6509,4865,9958,6411,1511,2085,9576,4799,4983,
	8323,6062,2648,9940,8883,1857,3876,2075,5985,1150,2288,9300,6077,6369,9082,105,268,3295,873,4290,3668,
	8525,3727,9334,3013,2568,2910,2605,8446,5809,4584,6993,6633,152,2064,7762,8962,6914,9149,6776,3538,
	6608,914,6298,880,3335,2970,1266,5095,8203,805,517,919,5619,1071,5871,1015,1401,8706,7594,3823,8899,
	1402,1200,8242,7887,3931,7225,8167,8650,5088,1539,1716,1011,6397,6950,1103,9852,1893,605,4090,4097,
	1740,1883,979,5554,4872,6189,8101,611,2501,6844,6557,1461,9328,1477,4054,7115,5378,6228,4166,8950,1061,
	7692,1821,9745,346,9288,6960,2284,8251,9610,679,4125,1578,5828,1119,8551,2782,9500,732,7482,7496,1680,
	9905,2714,931,608,1407,3997,7173,9623,7940,2267,3401,5701,4454,8175,4694,9364,7973,4371,1189,4896,1870,
	9662,6530,3567,8090,6280,2137,7295,8152,1325,18,9952,1722,6663,8805,9345,5831,8801,4090,5151,9930,798,
	4266,2500,5642,5154,3433,451,9035,1967,6131,2299,9888,3012,9712,7899,5133,9826,8177,8141,2559,366,7961,
	2626,7518,5110,6953,2509,7046,4998,3220,8903,2891,6377,7050,9962,6962,7244,5877,2787,4170,8014,885,1316,
	6500,6702,443,6583,5876,4321,5017,9754,4461,6530,6445,1478,7476,4414,2807,8526,5726,1516,7731,9814,2099,
	3083,4886,7142,954,5168,6340,5769,3316,5547,2766,6888,7245,7404,4851,8823,862,7846,2155,6533,8142,541,
	7780,2007,4541,2859,6374,3511,93,4518,5180,5836,1609,6150,6326,7463,3634,1010,2871,5198,7424,13,7497,
	6088,4044,5800,8250,5152,9710);
type
	TIndex=Longint;
function Power(A:TIndex;X:TIndex):TIndex;
begin
	A:=A mod Divisor;
	Result:=1;
	while X>0 do
	begin
		Dec(X);
		Result:=Result*A mod Divisor;
	end;
end;
procedure Main;
var
	P,N:TIndex;
	i:TIndex;
	F:TIndex;
begin
	Readln(N);
	P:=N div Interval;
	F:=LeadResult[P];
	for i:=P*Interval+1 to N do
	begin
		F:=(F-1)*Power(i,5)+Power(i,3)-Power(i,1)*F+3*Power(i,1)+7*F;
		F:=F mod Divisor;
		F:=(F+Divisor) mod Divisor;
	end;
	Writeln(F);
end;
begin
{$IFNDEF ONLINE_JUDGE}
	Assign(Input,'i.txt');
	Reset(Input);
	Assign(Output,'o.txt');
	Rewrite(Output);
{$ENDIF}
		Main;
{$IFNDEF ONLINE_JUDGE}
	Close(Input);
	Close(Output);
{$ENDIF}
end.