做了后面的题就知道前面的题怎么做了呢真棒_(:з」∠)_
Light OJ-
-1138 以为是找规律结果是是找因子个数哒
显然阶乘这种东西不是能一个一个查的，在下就打了个小表数了数零的个数，以为是逢5impossible其它以4个为周期。wa
找了网上一个大的表来验证自己的脑胡，对上述规律进行了修改。wa
好吧其实就是找因子中2*5的对数，因为2太多了所以我们数5就可以了。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; ll jg(ll n) { ll ans = 0; while (n) { ans += n / 5; n /= 5; } return ans; } int main() { int t, q; cin >> t; for (int i = 1; i <= t; i++) { cin >> q; int l = 0, r = 600000000; int mid,ans=0; while (l <= r) { mid = (l + r) >> 1; ll p = jg(mid); if (p == q) { ans = mid; r = mid-1; } else if (p > q)r = mid-1; else l = mid+1; } if (ans)printf("Case %d: %d\n", i, ans); else printf("Case %d: impossible\n", i); } return 0; }
存在性这种东西让二分来判就好惹。
-1370 买素数竹子（警告：这是一个拗口的笑话
找拥有互质数的个数不小于当前数的那个数，显然素数最优。
打个表，二分找找第一个比当前数大的质数（素数听起来像是豆制品），然后加起来就完事了。
#include<iostream> #include<cstdio> using namespace std; int p[80000]; bool isp[1000005]; int co; void pri() { co = 0; for (int i = 2; i < 1000005; i++)isp[i] = 1; for (int i = 2; i < 1000005; i++) { if (isp[i])p[++co] = i; for (int j = 1; j <= co && i*p[j] < 1000005; j++)isp[i*p[j]] = 0; } } int main() { pri(); int t; cin >> t; for (int i = 1; i <= t; i++) { int n, a; long long ans = 0; cin >> n; for (int j = 0; j < n; j++) { cin >> a; int l = 1, r = co,mid; while (l + 1 < r) { if (a == 1) {l = 0; break;} mid = (l + r) / 2; if (p[mid] > a)r = mid; else l = mid; } ans += p[l+1]; } printf("Case %d: %lld Xukha\n", i, ans); } return 0; }
然而红小豆还是re了，prime数组的大小记错了，开小了orz
-1213 真·幻视出题
一眼看出本质就完事了（不是我看的）
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; int n, mod, a; ll k; ll pm(ll a, ll b) { ll ans = 1; for (; b; b >>= 1, a = a * a%mod) if (b & 1)ans = ans * a%mod; return ans; } int main() { int t; cin >> t; for (int i = 1; i <= t; i++) { cin >> n >> k >> mod; ll ans = 0; for (int j = 0; j < n; j++) { cin >> a; ans += a; } printf("Case %d: %lld\n", i, ans*pm(n, k - 1)%mod *k%mod); } return 0; }
本质就是奇怪的排列组合啦，丢给组合数学队友就好了owo
-1236 一道之前做的不会的，后来做了别的题，再回来补发现是一个思路
然而红小豆还是wa了两发。因为表打小了。请打大小为范围的开方的表。
代码懒得贴了。和上一篇那个找拥有同一最小公倍数的对数的题完 全 一 样
-1197 学到了新东西(๑•̀ㅂ•́)و✧
超大的表，不会打..(｡•ˇ‸ˇ•｡)…
然后神仙教我米勒拉宾，
然后t了
然后神仙去找他曾经做过的类似题去了
然后红小豆打开了题解（补题就不要难为自己了(˘•ω•˘)）
然后 表 打 二 度
然后就会了(ŎдŎ；)
npb[1]=1;是精简板子之后遇到的第一个hack点，以后还是不能省略抹除0和1的存在啊(」＞＜)」
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int p[100005]; bool np[1000005],npb[1000005]; int co; void pri() { co = 0; np[1] = 1; for (int i = 2; i < 1000005; i++) { if (!np[i])p[co++]=i; for (int j = 0; j < co&&i*p[j] < 1000005; j++)np[i*p[j]] = 1; } } int main() { pri(); int t; cin >> t; ll a, b; for (int i = 1; i <= t; i++) { cin >> a >> b; ll ans = 0; if (b < 100005){ for (int j = a; j <= b; j++) if (!np[j])ans++; printf("Case %d: %lld\n", i, ans); } else { memset(npb, 0, sizeof(npb)); for (int j = 0; j < co&&p[j] <= b; j++) { ll q = a/ p[j]; if (q*p[j] < a)q++; for (ll k = q; k*p[j]<= b; k++) if (k!= 1)npb[k*p[j]- a] = 1; } for (int j = 0; j <= b - a; j++) if (!npb[j])ans++; printf("Case %d: %lld\n", i, ans); } } return 0; }
技能 表 打 二 度
效果 在打了个小一点的素数表只后通过取倍数获得各种非质数，然后捡起剩下的质数并发射出去
知道和被接受完全是两回事_(:з」∠)_