首页 > 代码库 > 【HDU5391】Zball in Tina Town

【HDU5391】Zball in Tina Town

【题目大意】

一个球初始体积为1,一天天变大,第一天变大1倍,第二天变大2倍,第n天变大n倍。问当第 n-1天的时候,体积变为多少。注意答案对n取模。

 

【题解】

根据威尔逊定理:(n-1)! mod n =-1

所以当n为质数时,答案就是n-1

否则答案显然是0

注意4要特判一下,ans[4]=2

这里有一种很魔性的判素数的方法,详见代码

 1 /*************
 2   HDU 5391
 3   by chty
 4   2016.11.4
 5 *************/
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<cstdlib>
10 #include<ctime>
11 #include<cmath>
12 #include<algorithm>
13 using namespace std;
14 int T,cnt(1),prime[100010];
15 inline int read()
16 {
17     int x=0,f=1;  char ch=getchar();
18     while(!isdigit(ch))  {if(ch==-)  f=-1;  ch=getchar();}
19     while(isdigit(ch))  {x=x*10+ch-0;  ch=getchar();}
20     return x*f;
21 }
22 bool isprime(int x)
23 {
24     for(int i=1;prime[i]*prime[i]<=x&&i<=cnt;i++) if(x%prime[i]==0)  return 0;
25     return 1;
26 }
27 int main()
28 {
29     freopen("cin.in","r",stdin);
30     freopen("cout.out","w",stdout);
31     T=read();  prime[1]=2;
32     for(int i=3;i<=100000;i++)  if(isprime(i))  prime[++cnt]=i;
33     while(T--)
34     {
35         int x=read();
36         if(x==4)  printf("2\n");
37         else if(isprime(x))  printf("%d\n",x-1);
38         else printf("0\n");
39     }
40     return 0;
41 }

 

【HDU5391】Zball in Tina Town