HackPluto's Blog

ACM数论

字数统计: 375阅读时长: 2 min
2019/08/09 Share

HDU

1164
水题 ,两种方法求解

1
int k=panduan(i);

是一个优化,避免调用函数过多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//欧拉函数
int panduan(int a)
{
for (int i=2; i<=sqrt(a); i++) {
if (a%i==0) {
return 0;
}
}
return 1;
}
int main() {
int a;
while (scanf("%d",&a)!=EOF) {
int i=2;
while (i<=a) {
int k=panduan(i);
if (k&&a==i) {
printf("%d\n",i);
break;
}
else if (k&&a%i==0) {
printf("%d*",i);
a/=i;
}
else
i++;
}

}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//筛法求素数
bool num[65536];
int su[8000];
void func1()
{
int k=0;
memset(num, 1, sizeof(num));
for (int i=2; i<65536; i++) {
if (num[i]==1) {
int j=i;
for (; j<65536; j+=i) {
num[j]=0;
}
su[k++]=i;
}
}
}
int main()
{
func1();
int a;
while (scanf("%d",&a)!=EOF) {
int i=0;
while(i<=8000) {
if ((a%su[i]==0)&&a!=su[i]) {
printf("%d*",su[i]);
a/=su[i];
}
else if (a==su[i]) {
printf("%d\n",a);
break;
}
else i++;
}
}
}

1211
这是一道关于RSA的题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
long long Exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
long long r=Exgcd(b,a%b,x,y);
long long t=x;
x=y;
y=t-a/b*y;
return r;
}
int main()
{
long long p,q,e,l;
while (scanf("%lld%lld%lld%lld",&p,&q,&e,&l)!=EOF) {
long long n=p*q,fn=(p-1)*(q-1),x,y;
Exgcd(e, fn, x, y);
x=(x%fn<0)?(x%fn+fn):x%fn;
while (l--) {
scanf("%lld",&y);
long long j=1;
for (int i=0; i<x; i++) {
j = (j*y)%n;
}
printf("%c",j%n);
}
}
}

CATALOG
  1. 1. HDU