《ACM-ICPC程序设计系列数论及其应用》例题个人答案记录

例1.1：HDU2099（2017/9/4）

本题书上给的答案是从0到99枚举，显然可以优化到每次递增b，这样至少可以把枚举次数减少到1/10。

 1 #include<cstdio>
 2 int a,b;
 3 int main()
 4 {
 5     while(scanf("%d%d",&a,&b) && a!=0 && b!=0)
 6     {
 7         a*=100;
 8         for(int cnt=0,now=a/b*b; now <= a+99; now+=b)
 9         {
10             if(a<=now && now<=a+99)
11             {
12                 if(++cnt != 1) printf(" ");
13                 printf("%02d",now%100);
14             }
15         }
16         printf("
");
17     }
18 }

View Code

例1.2：NEFU115 （2017/9/4）

本题暂时除了书上说的，没想到其他好办法，题目的要求使得我们根本不可能通过求斐波那契数列来解。

类似的也可以证明其余两个。

 1 #include<cstdio>
 2 int n;
 3 int main()
 4 {
 5     while(scanf("%d",&n)!=EOF)
 6     {
 7         if(n%12==0) printf("YES
");
 8         else
 9         {
10             if(n%4==0) printf("3
");
11             else if(n%6==0) printf("4
");
12             else printf("NO
");
13         }
14     }
15 }

View Code

例1.6：POJ1061（2017/9/15）

详见http://www.cnblogs.com/dilthey/p/7529257.html

例1.7：NEFU84（2017/9/17）

详见http://www.cnblogs.com/dilthey/p/7534710.html

例2.2：NEFU117（2017/9/17）

详见http://www.cnblogs.com/dilthey/p/7536800.html

例2.3：NEFU2（2017/9/21）

详见http://www.cnblogs.com/dilthey/p/7571967.html

例2.6：HDU2098（2017/9/22）

与例2.3如出一辙，稍作修改即可；

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #define MAX 16777220
 5 bool isPrime[MAX];
 6 int n;
 7 void screen()//埃筛求素数
 8 {
 9     memset(isPrime,1,sizeof(isPrime));
10     isPrime[0]=isPrime[1]=0;
11     int sqrt_MAX=(int)ceil(sqrt(MAX));
12     for(int i=2;i<=sqrt_MAX;i++)
13     {
14         if(isPrime[i]) for(int j=i*2;j<=MAX;j+=i) isPrime[j]=0;
15     }
16 }
17 int main()
18 {
19     screen();
20     while(scanf("%d",&n) && n!=0)
21     {
22         int cnt=0;
23         for(int i=1;i<=n/2;i++)
24         {
25             if(i!=n-i && isPrime[i] && isPrime[n-i]) cnt++;
26         }
27         printf("%d
",cnt);
28     }
29 }

View Code

例2.8：POJ2689（2017/9/22）

详见http://www.cnblogs.com/dilthey/p/7577275.html

例2.10：NEFU118（2017/9/24）

详见http://www.cnblogs.com/dilthey/p/7588382.html

《ACM-ICPC程序设计系列 数论及其应用》例题个人答案记录

《ACM-ICPC程序设计系列数论及其应用》例题个人答案记录