A.平方差公式后变为 n = (x + y)(x - y)
令 t = x - y ，变成
n = (t + 2x) * t，要 x 最小
O(sqrt(n)) 枚举 n 的因数即可
1 #include2 3 typedef long long ll; 4 5 ll n, m, k, t; 6 7 int main() { 8 scanf("%lld", &n); 9 while(n --) {10 k = 0;11 scanf("%lld", &m);12 for(ll i = 1;i * i < m;i ++) {13 if((m % i == 0) && ((m / i - i) % 2 == 0) ) {14 t = (m / i - i) / 2;15 k = 1;16 }17 }18 if(!k) puts("-1");19 else printf("%lld\n", t);20 }21 return 0;22 }
B.
C.如果GCD中间是加号会困难很多
乘号的话，我们枚举质数对ans的贡献即可
质数 pi 对结果的贡献就是
pow(pi，(n/pi)*(m/pi) + (n/pi^2)*(m/pi^2) + (n/pi^3)*(m/pi^3) +... )
最坏效率，1kw质数大约 n / ln(n) 个
pi = 2， 计算贡献需要logn次，快速幂约logn
复杂度约为 O(n / ln(n) * logn)，考虑到后面质数变大
pi > 100时， 计算贡献就只有3次了
实际计算贡献和快速幂平均下来不到2次
所以 n = 1kw 时是O(n)级别的
1 #include2 #include 3 4 using std::swap; 5 6 typedef long long ll; 7 8 int p[10000010], v[10000010]; 9 10 int tt;11 12 long long n, m, ans;13 14 const int Mod = 1e9 + 7;15 16 ll calc(ll x, ll k) {17 ll res = 1;18 for(;k > 0;x = x * x % Mod, k >>= 1)19 if(k & 1) res = res * x % Mod;20 return res;21 }22 23 int main() {24 for(int i = 2;i <= 10000000;i ++) {25 if(!v[i]) p[++ p[0]] = i;26 for(int j = 1;j <= p[0] && 1ll * i * p[j] <= 10000000;j ++) {27 v[i * p[j]] = 1;28 if(i % p[j] == 0) break;29 }30 }31 long long t, cnt;32 scanf("%d", &tt);33 while(tt --) {34 ans = 1;35 scanf("%lld %lld", &n, &m);36 if(m > n) swap(n, m);37 for(int i = 1;p[i] <= m && i <= p[0];i ++) {38 t = p[i], cnt = 0;39 while(1) {40 cnt += (n / t) * (m / t);41 if(m / t >= p[i]) t *= p[i];42 else break;43 }44 ans = ans * calc(p[i], cnt) % Mod;45 }46 printf("%lld\n", ans);47 }48 return 0;49 }
D.这个题今年3月刚写的又忘记了...
我们一个想法是分解质因数
得到 n! 里每个质数出现的最少次数
但我们平时分解质因数都是O(sqrt(n))的
即使使用前缀和，10^7也无法O(n^1.5)分解
所以这里用了一个巧妙又优秀的的O(nlogn)处理方法
1 for(int i = 2;i * i <= m;i ++) { 2 if(v[i]) continue; 3 for(int j = i * i;j <= m;j += i) 4 v[j] = -i; 5 } 6 for(int i = 2;i <= m;i ++) { 7 int j = i; 8 while(1) { 9 if(v[j] >= 0) {10 cout << j << endl;11 break;12 }13 else cout << -v[j] << endl, j /= -v[j];14 }15 } 当 i 为非质数时， -vis[i] 存的是 i 的最大的不大于sqrt(i)的质因数
分解质因数后可以二分
也可以用每个质数出现的个数得到不等式 n >= ci
实际效率约均为O(n)级别，前者思考复杂度低
1 #include2 3 #define rep(i, j, k) for(int i = j;i <= k;i ++) 4 #define rev(i, j, k) for(int i = j;i >= k;i --) 5 6 using namespace std; 7 8 typedef long long ll; 9 10 const int maxn = 10000010;11 12 int n, m, a[maxn], b[maxn], p[maxn];13 14 int v[maxn], num[maxn];15 16 ll cnt[maxn];17 18 bool judge(ll x) {19 ll y, c;20 rep(i, 1, p[0]) {21 y = x, c = 0;22 while(y) y /= p[i], c += y;23 if(c < cnt[i]) return 0;24 }25 return 1;26 }27 28 int main() {29 ios::sync_with_stdio(false);30 cin >> n;31 rep(i, 1, n) {32 cin >> a[i];33 m = max(m, a[i]);34 b[a[i]] ++;35 }36 for(int i = 2;i * i <= m;i ++) {37 if(v[i]) continue;38 for(int j = i * i;j <= m;j += i)39 v[j] = -i;40 }41 rep(i, 2, m)42 if(!v[i]) 43 p[++ p[0]] = i, num[i] = p[0];44 rev(i, m, 2)45 b[i] += b[i + 1];46 rep(i, 2, m) {47 int j = i;48 while(1) {49 if(v[j] >= 0) {50 cnt[num[j]] += b[i];51 break;52 }53 else cnt[num[-v[j]]] += b[i], j /= -v[j];54 }55 } 56 ll l = 1, r = 10000000000000ll, mid, ans;57 while(l <= r) {58 mid = (l + r) >> 1;59 if(judge(mid)) ans = mid, r = mid - 1;60 else l = mid + 1;61 }62 cout << ans;63 return 0;64 }
E.利用欧拉函数的性质，对于给定的 x
满足 phi[n] >= x 的最小的 n 一定是个质数
范围不大预处理即可
1 #include2 3 const int maxn = 1000010; 4 5 int pr[maxn], ph[maxn], vis[maxn]; 6 7 int Case, n, a, b[maxn]; 8 9 long long ans;10 11 int main() {12 for(int i = 2;i < maxn;i ++) {13 if(!vis[i]) {14 pr[++ pr[0]] = i;15 ph[i] = i - 1;16 }17 for(int j = 1;j <= pr[0] && i * pr[j] < maxn;j ++) {18 vis[i * pr[j]] = 1;19 if(i % pr[j] == 0) break;20 }21 }22 int last = 1000003;23 for(int i = 1000000;i;i --) {24 b[i] = last;25 if(ph[i]) last = i;26 }27 scanf("%d", &Case);28 for(int t = 1;t <= Case;t ++) {29 ans = 0;30 scanf("%d", &n);31 for(int j = 1;j <= n;j ++) {32 scanf("%d", &a);33 ans += b[a];34 }35 printf("Case %d: %lld Xukha\n", t, ans);36 }37 return 0;38 }
F.
G.求前几位的题目，取个对数就行
利用斐波那契数列的通项公式
我们发现后面减去的一项<1，n变大之后忽略即可
取完对数乘法变加法
最后输出前4位，必须舍去后面位数所以直接double转int
%.0f 会四舍五入并不满足要求
1 #include2 #include 3 #include 4 5 using std::abs; 6 7 int n, f[21]; 8 9 int main() {10 f[1] = 1;11 for(int i = 2;i < 21;i ++) f[i] = f[i - 1] + f[i - 2];12 while(scanf("%d", &n) != EOF) {13 if(n < 21) printf("%d\n", f[n] % 10000);14 else {15 double x = (log(1 / sqrt(5.0)) + log((sqrt(5.0) + 1) / 2) * n) / log(10.0);16 x -= (int)x;17 x = pow(10, x);18 while(x < 1000) x *= 10;19 printf("%d\n", (int)x);20 }21 }22 return 0;23 }
H.
I.混进来的放水题目
可以先把每一层节点都挂到上一层的一个节点上
可以出现最多的叶子节点
如果发现太多了就开始把当前层的节点
往上一层的其他节点上挪动，每动一次减少一个叶子节点
1 #include2 3 const int maxn = 200010; 4 5 int n, t, k, b[maxn], s[maxn], a[maxn]; 6 7 int main() { 8 s[1] = 2, s[0] = 1; 9 scanf("%d %d %d", &n, &t, &k);10 if(k > n - t) {11 puts("-1");12 return 0;13 }14 for(int j = 2,i = 1;i <= t;i ++) {15 scanf("%d", &a[i]), s[i + 1] = a[i] + s[i];16 for(int p = 1;p <= a[i];p ++, j ++)17 b[j] = s[i - 1];18 }19 k = n - t - k;20 if(k > 0) {21 for(int p = 2;p <= t;p ++) {22 for(int j = s[p - 1] + 1, i = s[p] + 1;i < s[p + 1] && j < s[p];i ++, j ++) {23 b[i] = j, k --;24 if(!k) break;25 }26 if(!k) break;27 }28 }29 if(k) puts("-1");30 else {31 printf("%d\n", n);32 for(int i = 2;i <= n;i ++)33 printf("%d %d\n", i, b[i]);34 }35 }
J.快速幂水题
另外因为2009非质数，所以不到50的时候ans已经变成0了
1 #include2 3 typedef long long ll; 4 5 ll n, a[3000]; 6 7 ll power(ll x, ll k) { 8 ll res = 1; 9 for(;k;k >>= 1, x = x * x % 2009)10 if(k & 1) res = res * x % 2009;11 return res;12 }13 14 int main() {15 ll m, ans;16 a[0] = 1, a[1] = 1;17 for(int i = 2;i < 2009;i ++)18 a[i] = a[i - 1] * i % 2009;19 while(scanf("%lld", &n) != EOF) {20 ans = 1;21 m = n / 2009;22 ans *= power(a[2008], m);23 printf("%lld\n", ans * a[n % 2009] % 2009);24 }25 return 0;26 }