威尔逊定理：
当且仅当p为
质数时：( p -1 )! ≡ -1 ( mod p )
或者这么写( p -1 )! ≡ p-1 ( mod p )
或者说
若p为质数，则p能被(p-1)!+1整除
hdu2973
YAPTCHA
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1031 Accepted Submission(s): 556
Problem Description
The math department has been having problems lately. Due to immense amount of unsolicited automated programs which were crawling across their pages, they decided to put Yet-Another-Public-Turing-Test-to-Tell-Computers-and-Humans-Apart on their webpages. In short, to get access to their scientific papers, one have to prove yourself eligible and worthy, i.e. solve a mathematic riddle.
However, the test turned out difficult for some math PhD students and even for some professors. Therefore, the math department wants to write a helper program which solves this task (it is not irrational, as they are going to make money on selling the program).
The task that is presented to anyone visiting the start page of the math department is as follows: given a natural n, compute
where [x] denotes the largest integer not greater than x.
Input
The first line contains the number of queries t (t <= 10^6). Each query consist of one natural number n (1 <= n <= 10^6).
Output
For each n given in the input output the value of Sn.
Sample Input
13
1
2
3
4
5
6
7
8
9
10
100
1000
10000
Sample Output
0
1
1
2
2
2
2
3
3
4
28
207
1609
思路：判断3k+7是否为质数，如果为质数那么该部分就为1，否则为0.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=1000110;
//int prime[maxn]; //第i个素数
bool is_prime[maxn*3]; //is_prime[i]为true表示i是素数
int ans[1000050];
int sieve(int n)
{
int p = 0;
memset(is_prime,true,sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++){
if (is_prime[i]){
// prime[p++] = i;
for (int j = 2 * i; j <= n; j += i)
is_prime[j] = false;
}
}
return p;
}
void init()
{
int p=sieve(maxn*3-5);
memset(ans,0,sizeof(ans));
for(int i=1;i<=1000000;i++)
{
if(is_prime[3*i+7])ans[i]=ans[i-1]+1;
else ans[i]=ans[i-1];
}
}
int main()
{
init();
int t;
int n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",ans[n]);
}
}
hdu5391
Zball in Tina Town
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 2620 Accepted Submission(s): 1237
Problem Description
Tina Town is a friendly place. People there care about each other.
Tina has a ball called zball. Zball is magic. It grows larger every day. On the first day, it becomes
1
time as large as its original size. On the second day,it will become
2
times as large as the size on the first day. On the n-th day,it will become
n
times as large as the size on the (n-1)-th day. Tina want to know its size on the (n-1)-th day modulo n.
Input
The first line of input contains an integer
T
, representing the number of cases.
The following
T
lines, each line contains an integer
n
, according to the description.
T≤105,2≤n≤109
Output
For each test case, output an integer representing the answer.
Sample Input
2
3
10
Sample Output
2
0
思路：判断n是否为素数，为素数就用威尔逊定理为n-1，否则为合数的话，可化为n=a1^q1*a2^q2*...*am^qm。这样对于每个ai^qi，必存在小于n的数，包含因子ai^1,ai^2,...,ai^(qi-1)，除n=4外，他们的乘积大于等于ai^qi，可判定答案就是0，n=4时特判为2.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
bool isPrime(int x)
{
for(int i=2;i*i<=x;i++)
{
if(x%i==0)return false;
}
return true;
}
int main()
{
int t;
int n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(isPrime(n))printf("%d\n",n-1);
else if(n==4)printf("2\n");
else printf("0\n");
}
}
