UPC2022暑期个人训练赛第19场(B,P)

B: 数学 (math)

大意：

求 n(n<=1e12) 分解为连续整数和的方案数

思路：

非常巧妙的一道数学题
我们假设连续整数和的首项为 $a$ ,一共有 $n$ 项 ，和为 $S$
则一定满足
$S=\frac{(首项+末项)\ast n}{2}$
化简就是
$2\ast S=(2\ast a+n-1)\ast n$
显然有两个未知数 $a$ 和 $n$
如果我们枚举$a$ 和 $n$ 一定会爆掉
1.分析 $n$ 的范围：
n 是项数，当$a=1$时 $n$ 最大 这时 $2\ast S=(n+1)\ast n$
所以我们可以得到 $n\ast n<(n+1)\ast n=2\ast S$
所以 $n<sqrt(2\ast S)$ n最大在 1.5e⁶ 左右
2.分析 $a$ 的范围：
而首项显然我们可以取到 $\frac{a}{2}$ 所以枚举两个值显然不合适
最大为2e¹¹
分析完复杂度后我们明显的可以看出要从$n$下手，枚举所有的 $n$ ,判断此时的首项是否合法即可
首项要是个正整数

#include
using namespace std;
       
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 2e5+10;
const int NN = 1e6+10;
const int pp = 1e9+7;
typedef pair<int,int>PII;
ll n,ans;
int main()
{
    cin>>n;
    for(ll i=2;i<=sqrt(n*2);i++)
    {
        ll k=((n*2)-i*i+i)%(i*2);
        if(k==0&&((n*2)-i*i+i)/(i*2)>0) ans++;
    }
    cout<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

问题 P: Count Interval

大意：

给出 N 个数，求满足下面式子的 l ，r 有多少组
$\sum _{i=l}^r{A}_i=k$

思路

我们可以用前缀和优化一下，优化完了之后就是求满足$sum[r]-sum[l-1]=k$的 l ， r 有多少组
这个题就变成了典型的 $A-B=k$ 问题；我们可以边存边计算，我们处理的每个数都是一个$A$,贡献就是前面数里$B$ 的数量 也就是 $A-K$ 的数量

A-B数对

#include
using namespace std;
       
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 2e5+10;
const int NN = 1e6+10;
const int pp = 1e9+7;
typedef pair<int,int>PII;
  
ll sum[N];
ll n,k,t,ans;
map<ll,ll>mp;
  
int main()
{
     
    cin>>n>>k;
     
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        sum[i]=sum[i-1]+t;
    }
     
    mp[0]=1;
     
    for(int i=1;i<=n;i++)
    {
        ans+=mp[sum[i]-k];
        mp[sum[i]]++;
//      cout<
    }
     
    cout<<ans;
     
      
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41