2018-计蒜之道-初赛-第五场

时间：2021-09-17 14:32:38

题目复制过来格式就不对了，可以去这个地方看题：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题比赛的时候还没做出来。。

标签：

相关文章