牛客练习赛14

好久不打比赛，就只能感觉到自己很菜了

链接：https://www.nowcoder.com/acm/contest/82/D
来源：牛客网

比较月亮大小

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

     点点是一名出色的狼人。众所周知，狼人只有在满月之夜才会变成狼。

    同时，月亮的大小随着时间变化，它的大小变化30天为一循环。它的变化情况(从第一天开始)为0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 然后又再一次循环。

    今年夏天点点很无聊，于是开始看月亮。由于点点很忙，所以他只选择一段连续的时间看月亮，并把月亮的大小记录了下来。

    现在，他告诉你他记录下东西，让你告诉他下一天(即点点记录下的最后一天的第二天)的月亮是比前一天(即点点记录下的最后一天)大还是小。

输入描述:

给你一个正整数n表示点点记录下的时间个数。
下一行n个自然数表示点点记录下的月亮大小。

输出描述:

一个字符串。
如果下一天的比前一天的大则输出"UP"
如果下一天的比前一天的小则输出"DOWN"
如果无法判断则输出"-1"

示例1

输入

5
3 4 5 6 7

输出

UP

示例2

输入

8
12 13 14 15 14 13 12 11

输出

DOWN

示例3

输入

1
8

输出

-1

备注:

n≤100 0 ≤ a _i ≤ 15

保证输入的数据满足月亮变化的循环规律

很快就会发现两个的时候怎么就是怎么啊，但是还有情况就是只有一个，而且最后一个是0或15，这个时候也是可以确定的

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==1)
    {
        int x;
        cin>>x;
        if(x==0)cout<<"UP";
        else if(x==15)cout<<"DOWN";
        else cout<<-1;
    }
    else
    {
        for(int i=0,x;i<n-2;i++)
            cin>>x;
        int x,y;
        cin>>x>>y;
        if(y==0||x<y&&y!=15)cout<<"UP";
        else cout<<"DOWN";
    }
}

链接：https://www.nowcoder.com/acm/contest/82/A
来源：牛客网

n的约数

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

t次询问，每次给你一个数n，求在[1,n]内约数个数最多的数的约数个数

输入描述:

第一行一个正整数t
之后t行，每行一个正整数n

输出描述:

输出t行，每行一个整数，表示答案

示例1

输入

5
13
9
1
13
16

输出

6
4
1
6
6

备注:

对于100%的数据，t <= 500 , 1 <= n <= 1000000000000000000

---

这个题数据量还是非常大的，难道要素因数分解？大素数分解能做是完全不可能的啊

其实因为约数可以可以求素因子来弄，然后乘法原理，最后会得到

若一个数N满足：N = A1N1 * A2N2 * A3N3 * …… * AmNm，则n的约数个数为(N1 + 1) (N2 + 1) (N3 + 1) …… (Nm + 1）

本来想只考虑四个素数的，但是错了，所以还是要循环优化下多来几个素数，因为乘法带来的增长更快，2*2*2*2才是最快的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,ans,p[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll n;
void la(ll m,int h,int k,int f)
{
    if(k>16)return;
    if(h>ans)ans=h;
    for(int i=1; i<=f; i++)
        if(m<=n/p[k])m*=p[k],la(m,h*(i+1),k+1,i);
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        ans=0,la(1,1,0,15);
        cout<<ans<<endl;
    }
    return 0;
}