集训暂时告一段落，我也跑回家里面了，慢慢的继续刷题吧：）
Uva10214
题意：有一个a*b的地图，每个整数坐标点都种着一棵树，你站在坐标系原点看四个象限，问最多能看到几个点
解法：
首先，四个象限一个性质，所以只统计第一个象限就行了。 其次，站在原点看，坐标为（x，y）的树能被看到的条件是gcd（x，y）= 1。
因为a的范围比较小，所以我们直接枚举a即可。那么，对于 1<=y<=x 有 phi[x]个，接着有公式gcd(kx+i,i)==gcd(x,i)，所以对于x的整数倍，我们直接计算，然后对于多出的那些部分直接暴力求解即可。
除此之外还应该记住两个定理：
一个数的所有素因子都大于M 等价于和 M!互素；
对于k>M，k与M互素当且仅当k%M与M互素
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 typedef long long ll; 5 const int maxn = 2e6 + 5; 6 int phi[maxn]; 7 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } 8 9 void generate_phi_table(int n, int *phi) { 10 for (int i = 2; i <= n; i++)phi[i] = 0; 11 phi[1] = 1; 12 for (int i = 2; i <= n; i++)if (!phi[i]) 13 for (int j = i; j <= n; j += i) { 14 if (!phi[j])phi[j] = j; 15 phi[j] = phi[j] / i*(i - 1); 16 } 17 return; 18 } 19 20 int main() { 21 int a, b; 22 generate_phi_table(2001, phi); 23 while (scanf("%d%d", &a, &b) && a&&b) { 24 ll ans = 0; 25 for (int i = 1; i <= a; i++) { 26 int k = b / i; ans += k*phi[i]; 27 for (int y = k*i + 1; y <= b; y++) { 28 ans += (gcd(i, y) == 1); 29 } 30 } 31 ll N = 1ll * (2 * a + 1) * (2 * b + 1) - 1; 32 printf("%.7f ", (double)1.0*(ans * 4 + 4) / N); 33 } 34 return 0; 35 }
Uva1642
题意：
给出一个长度在 100 000 以内的正整数序列，大小不超过 10^ 12。求一个连续子序列，使得在所有的连续子序列中，它们的GCD值乘以它们的长度最大。
解法：
这道题的思路和其他求区间应用的题还是有点像的，都是求所有区间的某个值的最大值。
这类题一般的思路是：枚举区间右边的起点，然后维护某个结构，使得减少左区间的枚举量。
这道题里面我们维护的是以j为起点的所有左区间里的各个gcd的值，每当增加a[j]的值，我们都先将所有的值维护一遍，再判断。
注意map中删除的操作，那个it++如果放到外面就会WA，多看看多感觉
1 #include<cstdio> 2 #include<map> 3 #include<algorithm> 4 using namespace std; 5 typedef long long ll; 6 typedef map<ll, ll>::iterator mpi; 7 const int maxn = 1e5 + 5; 8 map<ll, ll>mp; 9 ll a[maxn]; 10 ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); } 11 12 int main() { 13 int T; scanf("%d", &T); 14 while (T--) { 15 ll ans = 0; mp.clear(); 16 int n; scanf("%d", &n); 17 for (int i = 1; i <= n; i++)scanf("%lld", &a[i]); 18 for (int j = 1; j <= n; j++) { 19 if (!mp.count(a[j]))mp[a[j]] = j; 20 for (mpi it = mp.begin(); it != mp.end(); ) { 21 pair<ll, ll>now = *it; 22 ll new_gcd = gcd(now.first, a[j]); 23 ans = max(ans, new_gcd*(j - now.second + 1)); 24 if (!mp.count(new_gcd))mp[new_gcd] = now.second; 25 else mp[new_gcd] = min(mp[new_gcd], now.second); 26 if (new_gcd < now.first)mp.erase(it++); 27 else it++; 28 } 29 } 30 printf("%lld ", ans); 31 } 32 return 0; 33 }
Uva11040
题意：
求给出的数最近的两个素数的差，若给的数是素数，输出0。
解法：
打表后二分即可
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 7 //线性筛 8 bool visit[10100000]; 9 int prime[10000000]; 10 11 void generate_prim(int n){ 12 memset(visit, true, sizeof(visit)); 13 int num = 0; 14 for (int i = 2; i <= n; ++i){ 15 if (visit[i] == true){ 16 num++; 17 prime[num] = i; 18 } 19 for (int j = 1; ((j <= num) && (i * prime[j] <= n)); ++j){ 20 visit[i * prime[j]] = false; 21 if (i % prime[j] == 0) break; 22 } 23 } 24 } 25 26 int main() { 27 generate_prim(1300000); 28 int n; 29 while (scanf("%d", &n) && n) { 30 int pos = lower_bound(prime, prime + 100021, n) - prime; 31 if (prime[pos] == n)printf("0 "); 32 else printf("%d ", prime[pos]-prime[pos-1]); 33 } 34 return 0; 35 }
Uva1213
题意：
把n拆成k个不同素数的和，有多少种拆法。
解法：
打表后dp即可，这个dp的问题可以归纳为：在n个数中选k个数，使得和m的方案数
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 bool visit[10100000]; 6 int prime[10000000]; 7 int f[1130][200]; 8 9 int prime_num = 0; 10 void generate_prim(int n) { 11 memset(visit, true, sizeof(visit)); 12 for (int i = 2; i <= n; ++i) { 13 if (visit[i] == true) prime[++prime_num] = i; 14 for (int j = 1; ((j <= prime_num) && (i * prime[j] <= n)); ++j) { 15 visit[i * prime[j]] = false; 16 if (i % prime[j] == 0) break; 17 } 18 } 19 return; 20 } 21 22 void generate_plan() { 23 generate_prim(1300); 24 f[0][0] = 1; 25 for (int k= 0; k < prime_num; k++) { 26 for (int i = 1120; i >= 0; i--) { 27 int UP = lower_bound(prime, prime + k, i) - prime + 1; 28 for (int j = 1; j < UP; j++) { 29 if (prime[k] > i)break; 30 f[i][j] += f[i - prime[k]][j - 1]; 31 } 32 } 33 } 34 return; 35 } 36 37 int main() { 38 generate_plan(); 39 int n, m; 40 while (scanf("%d%d", &n, &m) && n&&m) { 41 printf("%d ", f[n][m]); 42 } 43 return 0; 44 }
Uva1210
题意：
計算連續素數的結合為n的組合有多少種。
解法：
由于10000以内素数的个数不超过1200，所以可以接受O(n^2)算法。
维护一个前缀和，然后在素数表中二分查找枚举的上界j，之后枚举每一个区间即可
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; bool visit[10100000]; int prime[10000000]; ll sum[10000 + 5]; int prime_num = 0; void generate_prim(int n) { memset(visit, true, sizeof(visit)); for (int i = 2; i <= n; ++i) { if (visit[i] == true) { prime[++prime_num] = i; sum[prime_num] += sum[prime_num - 1] + i; } for (int j = 1; ((j <= prime_num) && (i * prime[j] <= n)); ++j) { visit[i * prime[j]] = false; if (i % prime[j] == 0) break; } } return; } int main() { int n; generate_prim(10000); while (scanf("%d", &n) && n) { int pos = lower_bound(prime, prime + prime_num, n) - prime; int ans = 0; for (int j = pos; j >= 1; j--) { if (sum[j] < n)break; for (int i = 1; i <= j; i++) { ans += (sum[j] - sum[i - 1] == n); } } printf("%d ", ans); } return 0; }
Uva10539
题意：输入两个整数L，U，统计区间[L,U]中有多少个数满足：它本身不是素数，但只有一个素因子。
解法：
这里L和U的范围为1e12，开根号为1e6，之后暴力查找为logn，大约是13，所以可以接受
（论算复杂度的重要性
1 /* 2 算法复杂度为O(2nlogn)，可以接受 3 */ 4 #include<cstdio> 5 #include<algorithm> 6 #include<cstring> 7 using namespace std; 8 typedef long long ll; 9 bool visit[10100000]; 10 int prime[10000000]; 11 12 int prime_num = 0; 13 void generate_prim(int n) { 14 memset(visit, true, sizeof(visit)); 15 for (int i = 2; i <= n; ++i) { 16 if (visit[i] == true) { 17 prime[++prime_num] = i; 18 } 19 for (int j = 1; ((j <= prime_num) && (i * prime[j] <= n)); ++j) { 20 visit[i * prime[j]] = false; 21 if (i % prime[j] == 0) break; 22 } 23 } 24 return; 25 } 26 27 int main() { 28 generate_prim(1000000); 29 int T; scanf("%d", &T); 30 while (T--) { 31 ll L, R; scanf("%lld %lld", &L, &R); 32 int ans = 0; 33 for (int i = 1; i <= prime_num; i++) { 34 if (prime[i]*prime[i] > R)break; 35 for (ll j = 1ll*prime[i]*prime[i]; j <= R; j *= prime[i]) 36 ans += (j >= L&&j <= R); 37 } 38 printf("%d ", ans); 39 } 40 return 0; 41 }
Uva10622
题意：求使 x = b ^ p ,的最大的p
解法；
唯一分解定理。
首先如果n是负的话，就把n变成它的相反数。
求所有的素因子的最小公约数。再次，如果n是负数的话，需要将这个最小公约数累除2，直到它变成奇数
还有这个提交怎么这么烦，一会过一会T一会WA的，醉了
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef signed long long ll; 5 const int maxn = 100000; 6 int fac[maxn], frq[maxn]; 7 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } 8 9 int work_quality_factor(ll n, int quality_fac[], int frequency[]){ 10 ll res, temp, i; 11 res = 0; 12 temp = n; 13 for (i = 2; i*i <= temp; i++) 14 if (temp%i == 0) 15 { 16 quality_fac[res] = i; 17 frequency[res] = 0; 18 while (temp%i == 0) 19 { 20 temp = temp / i; 21 frequency[res]++; 22 } 23 res++; 24 } 25 if (temp > 1) 26 { 27 quality_fac[res] = temp; 28 frequency[res++] = 1; 29 } 30 return res; 31 } 32 33 int main() { 34 ll n; 35 while (scanf("%lld", &n) && n) { 36 int fac_num = work_quality_factor(n < 0 ? -n : n, fac, frq); 37 int ans = 0; 38 for (int i = 0; i < fac_num; i++) ans = gcd(ans, frq[i]); 39 if (ans == 0)ans = 1; 40 if (n < 0)while (!(ans % 2))ans /= 2; 41 printf("%d ", ans); 42 } 43 return 0; 44 }