例45  最大乘积

问题描述

给定一个整数 n，找到三个整数 x,y,z，要求满足 x+y+z=n且 x,y,z都能整除 n，且使得乘积xyz 的值最大，求 xyz的最大值。

输入格式

第一行为一个整数 T  (1≤T≤10⁶)，表示数据组数，接下去 T 行每行一个整数 n (1≤n≤10⁶)。

输出格式

如果存在满足条件的 x,y,z的值，输出其中 xyz的最大值，如果不存在满足条件的值，则输出−1。

输入样例

3

1

2

3

输出样例

-1

-1

1

        （1）编程思路。

先对较小的连续n值进行手算，如下。

N=3时，可分解为 1 1 1，乘积最大为1；

N=4时，可分解为1 1 2，乘积最大为2；

N=5时，找不出满足条件的分解；

N=6时，可分解为 2 2 2，乘积最大为8；

N=7时，找不出满足条件的分解；

N=8时，可分解为 2 2 4，乘积最大为16；

N=9时，可分解为3 3 3，乘积最大为27；

N=10，N=11时均找不出满足条件的分解；

        N=12时，可分解为4 4 4，乘积最大为64；当然也可分解为3 3 6，但乘积54，不是最大。

        由此，可以得到如下规律：如果n能整除3（n % 3 == 0），就把n分解成n/3+n/3+n/3；其次如果n能整除4（n % 4 == 0），就分解成n/4+n/4+n/2；其他情况都无解，输出-1即可。

（2）源程序。

#include <stdio.h>

int main()

{

    int t;

    scanf("%d",&t);

    while (t--)

    {

        long long n,ans;

        scanf("%lld",&n);

        if (n%3==0)

        {

            ans=(n/3)*(n/3)*(n/3);

            printf("%lld\n",ans);

        }

        else if (n%4==0)

        {

            ans=(n/4)*(n/4)*(n/2);

            printf("%lld\n",ans);

        }

        else

            printf("-1\n");

    }

     return 0;

}

习题45

45-1 余数求和

        本题选自洛谷题库 （https://www.luogu.org/problem/P2261）

题目描述

给出正整数 n 和k，计算 G(n, k)=k mod 1+k mod 2+k mod 3+⋯+k mod n 的值。其中k mod i 表示 k 除以 i 的余数。

例如 G(10, 5)= 5 mod 1+5 mod 2+5 mod 3+5 mod 4+5 mod 5⋯+5 mod 10=0+1+2+1+0+5+5+5+5+5=29

输入格式

两个整数n，k

输出格式

答案

输入样例

10 5

输出样例

29

        （1）编程思路。

        对于区间[1,n]中的一段连续的子区间[I,j]，如果除k的商相同，那么除k的余数是一个等差数列。这样每一段的余数都可以快速求出。

        具体方法为：对于k/i=p，找到最大的j，使n/j=p。不难发现，若p=0，则j=n。否则j=k/p。此时，k除以区间[I,j]中每个数的商均为p，余数构成一个等差数列，首项为k%i，尾项为k%j，项数为j-i+1，直接用等差数列求和公式求和。

        （2）源程序。

#include <stdio.h>

int main()

{

    int n,k,i,j;

    scanf("%d%d",&n,&k);

    long long sum=0;

    for (i=1;i<=n;i=j+1)

    {

        int p=k/i;

        if (p==0) j=n;

        else j=k/p<n?k/p:n;

        long long  ai=k%i;

        long long  aj=k%j;

        sum+=(j-i+1)*(ai+aj)/2;

    }

    printf("%lld\n",sum);

    return 0;

}

45-2  烧水问题

        本题选自洛谷题库 （https://www.luogu.org/problem/P1984）

题目描述

把总质量为1kg的水分装在n个杯子里，每杯水的质量均为(1/n)kg，初始温度均为0℃。现需要把每一杯水都烧开。我们可以对任意一杯水进行加热。把一杯水的温度升高t℃所需的能量为(4200*t/n)J，其中，“J”是能量单位“焦耳”。如果一旦某杯水的温度达到100℃，那么这杯水的温度就不能再继续升高，此时我们认为这杯水已经被烧开。显然地，如果直接把水一杯一杯地烧开，所需的总能量为(4200*100)J。

在烧水的过程中，我们随时可以在两杯温度不同的水之间进行热传递操作。热量只能从温度较高的那杯水传递到温度较低的那杯水。由于两杯水的质量相同，所以进行热传递操作之后，原来温度较高的那杯水所降低的温度总是等于原来温度较低的那杯水所升高的温度。

一旦两杯水的温度相同，热传递立刻停止。

为了把问题简化，我们假设：

1、没有进行加热或热传递操作时，水的温度不会变化。

2、加热时所花费的能量全部被水吸收，杯子不吸收能量。

3、热传递总是隔着杯子进行，n杯水永远不会互相混合。

4、热传递符合能量守恒，而且没有任何的热量损耗。

在这个问题里，只要求把每杯水都至少烧开一遍就可以了，而不要求最终每杯水的温度都是100℃。我们可以用如下操作把两杯水烧开：先把一杯水加热到100℃，花费能量(4200*100/2)J，然后两杯水进行热传递，直到它们的温度都变成50℃为止，最后把原来没有加热到100℃的那杯水加热到100℃，花费能量(4200*50/2)J，此时两杯水都被烧开过了，当前温度一杯100℃，一杯50℃，花费的总能量为(4200*75)J，比直接烧开所需的(4200*100)J少花费了25%的能量。

你的任务是设计一个最佳的操作方案使得n杯水都至少被烧开一遍所需的总能量最少。

输入格式

输入文件只有一个数n。

输出格式

输出n杯水都至少被烧开一遍所需的最少的总能量，单位为J，四舍五入到小数点后两位。

输入样例

2

输出样例

315000.00

          （1）编程思路。

        不妨设每杯水加热升温1℃需要消耗1J，并将沸腾温度100℃简记为a，则

        第1杯水需要消耗100J的能量，从0℃加热到a（100℃）；此时第2杯水温度为a；

        第2杯水需要消耗50J（=1/2*100J）的能量，因为第2杯水可以中和的最高温度为a/2=100℃/2=50℃，需要加热升温a/2（50℃）；此时第1杯水温度为a/2，第2杯水温度为a；

        第3杯水需要消耗37.5J（=3/4*50J）的能量，因为第3杯水可以中和的最高温度为（a/2/2+a）/2=(50℃/2+100℃)/2=62.5℃，需要加热升温37.5℃；此时第1杯水为a/4，第2杯水为5*a/8（=62.5℃），第3杯水温度为a；

        第4杯水需要消耗31.25J（=5/6*37.5J）的能量，因为第4杯水可以中和的最高温度为((a/4/2+5*a/8)/2+a)/2=11*a/16=68.75℃，需要加热升温5*a/16=31.25℃；此时第1杯水为a/8，第2杯水为5*a/16，第3杯水为11*a/16，第4杯水温度为a；

        ……

由此可推出如下规律。

设第i杯水需要消耗的能量为cost[i]，则有

cost[1]=420000.00/n

cost[2]=(1/2)*cost[1]

cost[3]=(3/4)*cost[2]

cost[4]=(5/6)*cost[3]

    ……   

cost[i+1]= (2*i-1)/(2*i)* cost[i]

        （2）源程序。

#include <stdio.h>

int main()

{

    int n;

    scanf("%d",&n);

    double cost=420000.00/n;

    double sum=0;

    for (int i=1;i<=n;i++)

    {

        sum+=cost;

        cost*=(2*i-1.0)/(2.0*i);

    }

    printf("%.2f\n",sum);

    return 0;

}

45-3  高位与最低位相等

        本题选自洛谷题库 （https://www.luogu.org/problem/P2110）

题目描述

给定两个正整数 L 和 R，数出到底有多少个这样的 X：L <= X <= R，且 X 的最高位与最低位相等（十进制下）。比如，2、101、329873可以是这样的 X，而23、4567就不是。

输入格式

一行，这一行包括两个整数 L 和 R（1<=L<=R<=10^18）。

输出格式

一行，这一行包括一个整数，即满足所述性质的 X 的个数。

输入样例

2 47

输出样例

12

         （1）编程思路。

        设函数sum（n）求从1到n中合法的X的个数。显然，当n<=9时，sum（n）=n。

        从10开始，每10个数分一组（10~19，20~29，…，100~109，…，2000~2009，…），每一组中有且只有一个合法的数X。这个很好理解，当最高位确定的时候，最低位有0~9十种情况，但只有与最高位相同的1种符合要求。

        因此，当n>=10时，sum（n）=9+n/10。

        需要特别注意的是，当n的个位数小于最高位的时候，sum(n)要减1。

        例如，当n=4123时，n所处的组（4120~4129）中4124是合法的X，但是取不到。

（2）源程序。

#include <stdio.h>

long long  sum(long long n)

{

    if (n<=9) return n;

    long long a=n%10;

    long long cnt=n/10+9;

    long long b=n;

    while (b>=10) b/=10;

    if (b>a) cnt--;

    return cnt;

}

int main()

{

    long long l,r;

    scanf("%lld%lld",&l,&r);

    printf("%lld",sum(r)-sum(l-1));

    return 0;

}