UPC2022 Summer Individual Training Game 19 (B, P)

B: 数学 (math)

大意：

求 n(n<=1e12) The number of scenarios to decompose into consecutive integer sums

思路：

Very clever math problem
We assume that the leading term of the sum of consecutive integers is $a$ ,一共有 $n$ 项 ,和为 $S$
则一定满足
$S=\frac{(首项+末项)\ast n}{2}$
化简就是
$2\ast S=(2\ast a+n-1)\ast n$
There are obviously two unknowns $a$ 和 $n$
如果我们枚举$a$ 和 $n$ it will explode
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$ 的范围：
And the first item is clearly available to us $\frac{a}{2}$ So it's obviously not appropriate to enumerate two values
最大为2e¹¹
After analyzing the complexity, we can clearly see what to do$n$下手,枚举所有的 $n$ ,It can be judged whether the first item at this time is legal
The first term must be a positive integer

#include<bits/stdc++.h>
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;
}

问题 P: Count Interval

大意：

给出 N 个数,Find the one that satisfies the following formula l ,r 有多少组
$\sum _{i=l}^r{A}_i=k$

思路

We can optimize it with prefix sum,After the optimization is completed, it is satisfied$sum[r]-sum[l-1]=k$的 l , r 有多少组
This question has become typical $A-B=k$ 问题;We can store and compute as we go,Every number we deal with is one$A$,Contribution is the first few miles$B$ 的数量 也就是 $A-K$ 的数量

A-B数对

#include<bits/stdc++.h>
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<<ans<<endl;
    }
     
    cout<<ans;
     
      
    return 0;
}