ABC052

[ABC052C] Factors of Factorial

题面翻译

给定正整数 $N \left( 1\leq N \leq 10 ^3 \right)$ 求 $N!$ 的约数个数。结果对 $10^9 + 7$ 取模

题目描述

整数 $ N $ が与えられます。 $ N! $ の正の約数の個数を $ 10^9+7 $ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $

输出格式

$ N! $ の正の約数の個数を $ 10^9+7 $ で割った余りを出力せよ。

样例 #1

样例输入 #1
3
样例输出 #1
4
样例 #2

样例输入 #2
6
样例输出 #2
30
样例 #3

样例输入 #3
1000
样例输出 #3
972926972
提示

制約

$ 1≦N≦10^3 $

Sample Explanation 1

$ 3! $ $ =6 $ です。$ 6 $ の正の約数は $ 1,2,3,6 $ の $ 4 $ 個なので、$ 4 $ を出力します。

思路

需要一点点数论知识（可惜我没有）。

思路转载自：[题解] AT2286 [ARC067A] Factors of Factorial - 洛谷专栏 (luogu.com.cn)

若一个正整数$n>1$，且可分解为一系列质因数的乘积： \[ n=\prod \limits_{i=1}^k {p}^{a_i}_i \] 则$n$约数的个数$f(n)$为： \[ f(n)=\prod \limits_{i=1}^k(a_i+1) \] 由于观察到数据并不大，$n\leq1000$，我们可以考虑从$1$到$n$，每乘到一个数时，都分解一次质因数，用一个$map$数组统计可分解的质因数个数。中间的每个数可以分解的质因数指数都加 1，到最后就统计出了$n!$的质因数分解形式。时间复杂度$O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
map<int,int> m;
//迭代器
map<int,int>::iterator p;
//分解质因数
void solve(ll n){
    for(int i=2;i<=n;i++){
        while(n%i==0){
            n/=i;
            //进行统计
            m[i]++;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;cin>>n;
    ll ans=1;
    for(int i=1;i<=n;i++)solve(i);
    for(p=m.begin();p!=m.end();p++){
        ans=ans*(p->second+1)%mod;
    }
    cout<<ans;
    return 0;
}

[ABC052D] Walk and Teleport

题面翻译

在东西方向延伸的直线上，有N个城市。城市坐标按从西到东递增。

你现在在某个城市里，想去其他所有的城市。移动的方法有以下两种。

一，在直线上按东西方向平移，每移动一个单位距离疲劳值加A

二，直接瞬移到某个坐标，并且疲劳值加B

请使用以上两种方式直到去完其他所有的城市，并求出最小的疲劳值。

输入输出格式

输入格式：

第一行三个数,即N,A,B,

第二行N个数，即X[1],X[2]...,X[N]。

输出格式：

输出最小的疲劳值。

说明

2<=N<=1e5

1<=Xi,A,B<=1e9且X(i)<X(i+1)

题目描述

東西方向にのびる直線上に、$ N $ 個の町があります。町には、西から順に $ 1 $ から $ N $ までの番号がついています。直線上には座標が設定されていて、東に行くほど座標が大きくなります。町 $ i $ の座標は $ X_i $ です。

あなたは今、町 $ 1 $ にいて、これからほかの全ての町を訪れたいです。移動する手段は次の $ 2 $ 種類あります。

直線上を歩いて移動する。東西どちらに歩いても、$ 1 $ 移動する度に疲労度が $ A $ 上がります。

好きな場所へテレポートする。テレポートをすると、移動した距離によらず疲労度が $ B $ 上がります。

この $ 2 $ 種類の移動を繰り返して全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるか求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A $ $ B $ $ X_1 $ $ X_2 $ $ ... $ $ X_N $

输出格式

全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるかを出力せよ。

样例 #1

样例输入 #1
4 2 5
1 2 5 7
样例输出 #1
11
样例 #2

样例输入 #2
7 1 100
40 43 45 105 108 115 124
样例输出 #2
84
样例 #3

样例输入 #3
7 1 2
24 35 40 68 72 99 103
样例输出 #3
12
提示

制約

入力は全て整数である

$ 2≦N≦10^5 $

$ 1≦X_i≦10^9 $

全ての $ i(1≦i≦N-1) $ について、$ X_i < X_{i+1} $ が成り立つ

$ 1≦A≦10^9 $

$ 1≦B≦10^9 $

Sample Explanation 1

町 $ 1 $ から町 $ 2 $ まで $ 1 $ の距離歩いて移動したあと、町 $ 3 $ にテレポートし、そこから町 $ 4 $ まで $ 2 $ の距離歩いて移動すると、疲労度の上昇値の合計が $ 2×1+5+2×2=11 $ になり、これが最小です。

Sample Explanation 2

町 $ 1 $ から町 $ 7 $ まで歩き続けると、疲労度の上昇値の合計が $ 84 $ になり、これが最小です。

Sample Explanation 3

どのような順番でもよいので、$ 6 $ 回のテレポートで全ての町を訪れると、疲労度の上昇値の合計が $ 12 $ になり、これが最小です。

思路

一眼的贪心

题解区发现一篇奇怪的题解：[题解 AT2287 【ARC067B] Walk and Teleport】 - 洛谷专栏 (luogu.com.cn)，可以看看。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
int x[MAXN];
ll a,b;
int main(){
    ios::sync_with_stdio(false);
    int n;cin>>n;
    cin>>a>>b;
    ll ans=0;
    for(int i=1;i<=n;i++)cin>>x[i];
    for(int i=2;i<=n;i++){
        if(a*(x[i]-x[i-1])<b)ans+=a*(x[i]-x[i-1]);
        else ans+=b;
    }
    cout<<ans;
    return 0;
}