洛谷比赛：T226229 等差数列

提交13.78k   通过10   时间限制1.00s   内存限制128.00MB

(好了兄弟们，知道这题的恐怖了吗？）

题目描述

给你一个长为 n，首项为 a，公差为 d 的等差数列 x。

从 x 中任选两个数 xi​,xj​（i!=j），同时满足：

• xi​+xj​ 为偶数。

• x 中没有 (xi+xj)/2。

那么你就可以将 (xi+xj)/2 加入 x 中，称为一次操作。

注意：新加入的数也可被选择 。

问你最多能进行几次操作？

输入格式

本题有多组测试数据。

第一行一个正整数 T，表示测试数据组数。

对于每组测试数据，一行三个整数 n,a,d。

输出格式

对于每组测试数据，一行一个整数表示最多的操作次数。

输入输出样例

输入 

2
3 1 1
2 2 2

输出 

0
1

说明/提示

【样例 11 说明】

对于第一组数据，x=[1,2,3]，无法进行任何操作。

对于第二组数据，x=[2,4]，可以选择 2 和 4，将 （2+4）=3 加入数列中。

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（10 points）：d=1。
• Subtask 2（10 points）：n=2。
• Subtask 3（30 points）：T≤10，n×d≤1000，a=0。
• Subtask 4（50 points）：无特殊限制。

对于 100% 的数据，1≤T≤10^5，2≤n≤10^9，10^9≤a≤10^9，1≤d≤10^9。

首先我们来分析一下这个东西，我们先考虑n为2,a为0的情况，要添加几个数？

d（1-10）

1 2 3 4 5 6 7 8 9 10

1:0

2:1

3:0

4:3

5:0

6:1

7:0

8:7

9:0

10:1

先考虑添加数为0的情况：

1 3 5 7 9

及d为素数的情况下，添加数均为0；

还有d为3^n(1<=n<=10000000)时，添加数均为0；

再考虑添加数不为0的情况：

我们可以看到

2:1

4:3

8:7

6:1

10:1

懂了吗兄弟们（规律出来了）

及如果这个数%2==0，除以一个2，不断循环直到%2！=0；

1 3 7 15............。

如果这个数%3==0，除以一个3，不断循环直到%3！=0；

不变。

当然刚刚所有的分析是鉴于n=2的情况

如果不是n!=2的话，我们就把添加数乘以（n-1)。

#include <stdio.h>
#include <stdlib.h>
int isprime(int x)
{
    if(x==1)
    {
        return 1;
    }
    if(x==2)
    {
        return 0;
    }
    for(int i=2;i<x;i++)
    {
        if(x%i==0)
        {
            return 0;
        }
    }
    return 1;
}
int issanci(float x)
{
    while(x!=0)
    {
        if(x/3==1)
        {
            return 1;
            break;
        }
        x=x/3;
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t>=1)
    {
        int n,a,d;
        scanf("%d %d %d",&n,&a,&d);
        int flag1=isprime(d);
        int flag2=issanci(d);
        if(flag1==1)                           //是素数
        {
            printf("0\n");
        }
        else if(flag2==1)                      //是3的次方
        {
            printf("0\n");
        }
        else if(flag1!=1||flag2!=1)           //不是素数或者不是3的次方
        {
            int temp=d;
            int index=0;
            while(temp%2==0)
            {
                temp=temp/2;
                index=2*index+1;
            }
            while(temp%3==0)
            {
                temp=temp/3;
            }
            printf("%d\n",(n-1)*index);
        }
        t--;
    }
    return 0;
}

虽然这个代码从思路上是没问题的，但是时间肯定不够，我们需要大改一下。

这个时间复杂度应该足够小了。

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t>=1)
    {
        int n,a,d;
        scanf("%d %d %d",&n,&a,&d);
        if(d%2==1)                           //不是偶数
        {
            printf("0\n");
        }
        else if(d%2==0)           //是偶数
        {
            int temp=d;
            long long index=0;
            while(temp%2==0)
            {
                temp=temp/2;
                index=2*index+1;
            }
            printf("%lld\n",(n-1)*index);
        }
        t--;
    }
    return 0;
}