寒假Day3：Codeforces230+466思维题

1、题目链接：http://codeforces.com/contest/230/problem/B

题意：判断每个数是否只含三个因子，是输出YES，否则输出 NO

简单的素数打表，但是我一直错。。。错的原因在于。。。数组范围。。。

注意一下：

判断素数记得特判 1；
数据过大的时候用map进行标记；
bool 标记可以到10⁷，int 标记到10^6；
打表的时候双层for循环若是到N，数组开的大小需要N+；　　　　
sqrt处理会损失精度

 1 #include<bits/stdc++.h>
 2 using namespace  std;
 3 typedef long long ll;
 4  
 5 const int N=1e6+100;
 6 const int M=1e5+20;
 7 const int N1=1e6+20;
 8 ll a[M];
 9 bool book[N];
10 map<ll,int>m;
11 void init()
12 {
13     book[0]=1;
14     book[1]=1;
15     for(int i=2; i<=N1; i++)
16     {
17         if(book[i]==0)
18         {
19             for(int j=i+i; j<=N1; j+=i)
20             {
21                 book[j]=1;
22             }
23         }
24     }
25  
26     for(ll i=2;i<=N1;i++)
27     {
28         if(book[i]==0)
29         {
30             ll w=i*i;
31             m[w]=1;
32         }
33     }
34 }
35  
36 int main()
37 {
38     init();
39     int n;
40     ll x;
41     scanf("%d",&n);
42     for(int i=0;i<n;i++)
43     {
44         scanf("%lld",&x);
45         if(m[x])
46             printf("YES\n");
47         else
48             printf("NO\n");
49     }
50     return 0;
51 }

View Code

2、题目链接：http://codeforces.com/problemset/problem/466/A

这题很简单，关键在于我始终没翻译出这句话。。。

The single line contains four space-separated integers n, m, a, b (1 ≤ n, m, a, b ≤ 1000) 
— the number of rides Ann has planned, 
the number of rides covered by the m ride ticket, 
the price of a one ride ticket 
and the price of an m ride ticket.

翻译：坐地铁共坐n站，做m站要b元，一站要a元，问最少要多少钱

TO DO LIST：

w 50+
cfs*2

原来bridge the gap 不是建立矛盾。。是消除差距。。。见识短浅啊。。。