地址：http://acm.hdu.edu.cn/diy/contest_show.php?cid=21203
这次的题全是数论，很多都不会，还好题目不难
A题：HDU 1395
n为偶数和为1时没答案，n为奇数暴力即可
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
#define PI acos(-1)
using namespace std;
int main()
{
int n,i,m,flag;
while(scanf("%d",&n)!=EOF)
{
if(n%2==0||n==1) printf("2^? mod %d = 1\n",n);
else
{
flag=0;
m=2;
for(i=2;i<30000;i++)
{
m=(m%n)*2;
if(m%n==1)
{
flag=1;
printf("2^%d mod %d = 1\n",i,n);
break;
}
}
if(!flag) printf("2^? mod %d = 1\n",n);
}
}
return 0;
}
B题： HDU 2161 素数打表
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
#define PI acos(-1)
using namespace std;
int main()
{
int n,i,m,flag;
while(scanf("%d",&n)!=EOF)
{
if(n%2==0||n==1) printf("2^? mod %d = 1\n",n);
else
{
flag=0;
m=2;
for(i=2;i<30000;i++)
{
m=(m%n)*2;
if(m%n==1)
{
flag=1;
printf("2^%d mod %d = 1\n",i,n);
break;
}
}
if(!flag) printf("2^? mod %d = 1\n",n);
}
}
return 0;
}
C题：HDU 2674
发现规律，41以上全是0
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
#define PI acos(-1)
using namespace std;
int main()
{
int n,i,sum;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
{
printf("1\n");
continue;
}
if(n>=41)
{
printf("0\n");
continue;
}
sum=1;
sum*=(n%2009);
for(i=2;i<n;i++)
{
sum*=(i%2009);
sum%=2009;
}
printf("%d\n",sum);
}
return 0;
}
D题：HDU 1576
先让B对9973取余，然后直接暴力
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
#define PI acos(-1)
using namespace std;
int main()
{
int i,n,b,t,a;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&b);
b%=9973;
for(i=1;;i++)
{
a=i*9973+n;
if(a%b==0) break;
}
printf("%d\n",(a/b)%9973);
}
return 0;
}
E题：HDU 1262
把素数存起来直接算，取差最小
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
#define PI acos(-1)
#define LEN 10005
using namespace std;
int sushu[10000],a[50000];
int k=0;
bool notPrime[LEN];
void makeprime()
{
notPrime[1] = true;
for(int i = 2; i <= LEN; i++)
{
if(!notPrime[i])
{
sushu[k++]=i;
for(int j = 2 * i; j <= LEN; j += i)
{
notPrime[j] = true;
}
}
}
}
int main()
{
memset(notPrime,false,sizeof(notPrime));
makeprime();
int n=0,i,j,maxm,x,y,xx,yy,m;
while(scanf("%d",&a[n++])!=EOF);
for(i=0;i<n-1;i++)
{
maxm=10000;
m=(k+1)/2;
for(j=0;j<k;j++)
{
if(sushu[j]>a[i]) break;
if(!notPrime[a[i]-sushu[j]])
{
x=sushu[j];
y=a[i]-sushu[j];
if(y-x<maxm&&y-x>=0)
{
maxm=y-x;
xx=x;
yy=y;
}
}
}
printf("%d %d\n",xx,yy);
}
return 0;
}
F题： HDU 1163
本来发现了规律，可以一个一个相乘，得出根然后用根再乘，最后结果一样，可是当时脑抽算错了。这个是个对9取余的技巧，似乎以前POJ上遇到过
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
#define PI acos(-1)
using namespace std;
int main()
{
int n,i;
int m;
while(scanf("%d",&n),n)
{
m=n;
for(i=1;i<n;i++)
{
m=(m*n)%9;
}
if(m)
printf("%d\n",m);
else
printf("9\n");
}
return 0;
}
G题：HDU 2824
欧拉函数，百度的
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
#define PI acos(-1)
#define N 3000005
using namespace std;
int phi[N];
char prime[N];
/*
int main(int argc, const char *argv[])
{
prime = (char*)malloc((N + 1) * sizeof(char));
prime[0] = prime[1] = 0;
for(int i = 2; i <= N; i++)
prime[i] = 1;
for(int i = 2; i + i <= N; i++)
if(prime[i])
for(int j = i + i; j <= N; j += i)
prime[j] = 0;
//这段求出了N内的所有素数
phi = (int*)malloc((N + 1) * sizeof(int));
for(int i = 1; i <= N; i++)
phi[i] = i;
for(int i = 2; i <= N; i++)
if(prime[i])
for(int j = i; j <= N; j += i)
phi[j] = phi[j] / i * (i - 1); //此处注意先/i再*（i-1)，否则范围较大时会溢出
}
*/
int main()
{
int a,b,i;
long long int sum;
memset(prime,true,sizeof(prime));
prime[0] = prime[1] = false;
for(int i = 2; i + i <= N; i++)
if(prime[i])
for(int j = i + i; j <= N; j += i)
prime[j] = false;
for(int i = 1; i <= N; i++)
phi[i] = i;
for(int i = 2; i <= N; i++)
if(prime[i])
for(int j = i; j <= N; j += i)
phi[j] = phi[j] / i * (i - 1);
while(scanf("%d%d",&a,&b)!=EOF)
{
sum=0;
for(i=a;i<=b;i++)
sum+=phi[i];
printf("%I64d\n",sum);
}
return 0;
}
小结：这次周赛题目比较简单，虽然数论平时练习的不多，这次的题总算做完了，主要还是因为题目简单，时间花的略长