题目复制过来格式就不对了,可以去这个地方看题:https://www.jisuanke.com/contest/1232
A. 贝壳找房搬家
贝壳找房换了一个全新的办公室,每位员工的物品都已经通过搬家公司打包成了箱子,搬进了新的办公室了,所有的箱子堆放在一间屋子里(这里所有的箱子都是相同的正方体),我们可以把这堆箱子看成一个 x \times y \times zx×y×z 的长方体。
贝壳找房的leader
觉得所有的箱子放在一间房子里有点太挤了,不方便每个员工搬运自己的物品,于是又让搬家公司把这堆箱子的前面、后面、左边、右边、顶上各取走了一层放到其他屋子里。
当搬家公司搬完物品之后,贝壳找房的leader
知道剩下了多少个箱子,但是不知道搬家公司又搬运了多少个箱子,那么请问搬家公司最少和最多搬走了多少个箱子?
输入格式
第一行一个整数 TT,表示数据组数。
每组数据中,一个正整数 nn 代表剩余箱子的数目。
输出格式
输出 TT 行,每行两个正整数 min,maxmin,max,代表最少和最多搬走的箱子数。
数据范围
对于 100\%100% 的数据,1\le n\le10^6,T\le 100001≤n≤106,T≤10000。
样例解释
第一组数据
最小可能是 2\times4\times4=322×4×4=32 块,那么搬走之后就是 (2 - 1)\times(4 - 2)\times(4 - 2) = 4(2−1)×(4−2)×(4−2)=4块,而最多可能是5\times3\times3=455×3×3=45 块。
样例输入
2 4 100
样例输出
28 41 145 809
主要考察枚举,这个题就是解方程(x - 2) * (y - 2) * (z - 1) = n,然后找到 x * y * z - n的最大值和最小值即可。最容易想到的是3个循环枚举,但是数据量太大了,n是10^6,而且还有T组数据,T最多有10^4组,如果这样枚举时间复杂度就是10^10了,1秒肯定跑不完。
可以改善一下枚举方式,减少枚举的次数。可以考虑(x - 2)、(y - 2)、(z - 1),这3项里的每一项都是n的约数,所以我们可以先求出来n的约数有哪些,然后枚举所有的组合就求出来x、y、z的值了,然后再求x * y * z - n的最大值和最小值。注意求约数的时候只用枚举到sqrt(n)。
#include <cstdio> #include <algorithm> #include <cmath> #include <vector> #define MAX 1000001 using namespace std; int main() { int T; scanf( "%d", &T ); while( T-- ) { long long n; long long Max = 0; long long Min = 0x7fffffff; scanf( "%lld", &n ); vector<long long> vec; for( long long i = 1; i <= sqrt( n ); i++ ) { if( n % i == 0 ) { vec.push_back( i ); vec.push_back( n / i ); } } int len = vec.size(); for( int i = 0; i < len; i++ ) { for( int j = 0; j < len; j++ ) { for( int k = 0; k < len; k++ ) { long long t = vec[i] * vec[j] * vec[k]; if( t == n ) { long long z = vec[i] + 1; long long x = vec[j] + 2; long long y = vec[k] + 2; //printf( "%lld %lld %lld\n", vec[i] + 1, vec[j] + 2, vec[k] + 2 ); Min = min( x * y * z, Min ); Max = max( x * y * z, Max ); } } } } printf( "%lld %lld\n", Min - n, Max - n ); } return 0; }
B. 贝壳找房算术(简单)
贝壳找房力求为每位用户找到满意的房子,最近贝壳找房通过大数据得出下面的一个结论,
求满足 0<i,j \le n,0<i,j≤n, f(i) \times f(j)>0f(i)×f(j)>0 且 0< gcd(f(i),f(j)) \le k0<gcd(f(i),f(j))≤k 的数对 (i,j)(i,j) 的数量,其中满足条件的对数就是可以满足某位用户的房源数目。
其中 f(x)f(x) 表示 xx 所有数位的积,比如 f(124)=1 \times 2 \times 4=8f(124)=1×2×4=8。
因答案很大,请求出其在模 998244353998244353 意义下的结果。其中 gcd(x, y)gcd(x,y) 表示 xx 和 yy 的最大公约数。
提示: 其中 (1,2)(1,2) , (2,1)(2,1) 算是两种情况。
输入格式
一行两个正整数,分别表示 nn 和 kk。
保证 1 \le n \le 10001≤n≤1000,1 \le k \le 10^{18}1≤k≤1018。
输出格式
一个整数表示答案。
样例输入
9 5
样例输出
77
B题数据量比较小,所以只要暴力即可。两重循环枚举i和j,然后求gcd。
#include <cstdio> #include <algorithm> #include <map> using namespace std; long long gcd( long long a, long long b ) { if( b == 0 ) return a; return gcd( b, a % b ); } long long f( long long x ) { long long ans = 1; while( x ) { ans = ans * ( x % 10 ); x = x / 10; } return ans; } int main() { long long n, k; scanf( "%lld%lld", &n, &k ); long long cnt = 0; for( long long i = 1; i <= n; i++ ) { for( long long j = 1; j <= n; j++ ) { long long fi = f( i ); long long fj = f( j ); if( fi == 0 || fj == 0 ) continue; long long g = gcd( fi, fj ); if( g > 0 && g <= k ) { cnt = ( cnt + 1 ) % 998244353; } } } printf( "%lld\n", cnt ); return 0; }
C. 贝壳找房算术(中等)
保证 1 \le n \le 10^61≤n≤106,1 \le k \le 10^{18}1≤k≤1018
题面和B是一样的,就是数据范围不一样。如果C题用暴力就GG了,会超时。同样需要优化枚举的方式,可以发现有许多东西是重复的,比如f(135)和f(153)的结果就是一样的,所以有很多的重复操作。可以先把1-n的所有f(i)都算出来放进vector,使用map记录f(i)重复的次数,然后统计结果的时候遍历vector,结果进行乘法。
#include <cstdio> #include <algorithm> #include <map> #include <vector> using namespace std; long long gcd( long long a, long long b ) { if( b == 0 ) return a; return gcd( b, a % b ); } long long f( long long x ) { long long ans = 1; while( x ) { ans = ans * ( x % 10 ); x = x / 10; } return ans; } vector<long long> vec; map<long long, long long> mp; int main() { long long n, k; scanf( "%lld%lld", &n, &k ); long long cnt = 0; for( long long i = 1; i <= n; i++ ) { long long fi = f( i ); if( fi != 0 ) { if( mp.count( fi ) ) mp[fi]++; // 如果有重复就++ else { vec.push_back( fi ); mp[fi] = 1; // 还没重复的就放进vector,并让mp[fi] = 1 } } } // 枚举f(i)和f(j) for( int i = 0; i < vec.size(); i++ ) { for( int j = 0; j < vec.size(); j++ ) { long long g = gcd( vec[i], vec[j] ); if( g > 0 && g <= k ) { // 这里是乘法 cnt = ( cnt + mp[vec[i]] * mp[vec[j]] ) % 998244353; } } } printf( "%lld\n", cnt ); return 0; }
D题比赛的时候还没做出来。。