东北大学2021校赛6题：香辣牛肉面（数学+思维）

本文主要是介绍东北大学2021校赛6题：香辣牛肉面（数学+思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
现场做题历程：先是想到枚举C从0到F-1,将题转化成了把F-C分解成两个数相乘有多少种方法，当然先质因数分解，然后找规律，发现分解成p1ⁿ¹ p2ⁿ² * … pm^nm 以后，有(n1+1)(n2+1)(n3+1)…(nm+1) 种拆法。果断先写了一发暴力，当然是超时的。先上一份超时代码，复杂度O(n*logn)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//vector<string>v;
ll solve(ll x){if(x==1)return 1;if(x==2)return 2;ll cnt=1,i;for(i=2;i<=x;i++){ll t=0;while(x%i==0){x/=i;t++;}cnt*=(t+1);}//if(x>i)return 2;return cnt;
}
int main()
{//cout << "Hello world!" << endl;//init();int T;cin>>T;while(T--){// v.clear();ll N;ll ans=0;cin>>N;for(int C=0;C<N;C++){ll t=N-C;ans+=solve(t);}cout<<ans<<endl;}return 0;
}

然后发现超时太离谱了，这题数据1e12，能接受最高复杂度是O(sqrt(n))，说明思路一开始就有问题，然后开始转换思维的角度，想一想如何枚举V*S。想到前几天刚学最优化方法化不等式为等式标准型，比如x1+x2<=10，可以引入新变量x3转换为x1+x2+x3=0，然后这题正好反过来，把等式化为不等式，于是把问题转换为V * S<=F的所有情况 V 和 S 组合，然后就发现重大规律。当时就想，1 * 1到1 * F都满足，2 * 1 到2 * (F/2)都满足，那不就相当于求N/1+N/2+…+N/N,然后就写了一发直接求和，继续超时，复杂度O(n)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//vector<string>v;int main()
{//cout << "Hello world!" << endl;//init();int T;cin>>T;while(T--){// v.clear();ll N;ll ans=0;cin>>N;for(ll i=1;i<=N;i++){ans+=N/i;}cout<<ans<<endl;}return 0;
}

然后想怎么优化O(n)到O(sqrt(n))了，首先有一个优化到sqrt(n)的经典例子就是判断素数，假设a*b=x，则必有a<=b或b<=a，于是只需要求出小的因子，就能知道x是合数。这个是利用对称性，减小运算。本来这里也能用相似方法瞬间优化的，可惜考场上对着N/1+N/2+…+N/N这个向下取整的式子，硬是没想出来。实际上现在只要回退到前一步，考虑1 * F和F * 1可以同时算，1 * (F-1)和(F-1) * 1可以同时算，最后1 * 1只有一个，同理，2 * (F/2)和(F/2) 2可以同时算，最后22算一个，然后1 * 2 和2 * 1已经算过了，要减去2，以此类推就能求解。最后是

 ll ans=0;for(ll i=1;i*i<=n;i++){ans+=2*(n/i-i)+1;}cout<<ans<<endl;

当时虽然ac了但是推的不是上面这个简洁的规律，推了一个大数才能成立的O(sqrt(n))的规律，小数直接暴力O(n)，组合起来才AC，哭哭，当时要是能想到类比分解质数优化，不要直接抽象成求和就好了
现场AC代码，规律很复杂，不多说了，直接采取前一条就好

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;int main()
{//cout << "Hello world!" << endl;int T;cin>>T;while(T--){// v.clear();ll N=1;cin>>N;//while(N--){if(N==0){cout<<0<<endl;continue;}if(N==1){cout<<1<<endl;continue;}if(N==2){cout<<3<<endl;continue;}if(N==3){cout<<5<<endl;continue;}if(N<=1000){ll ans2=0;for(ll i=1;i<=N;i++){ans2+=N/i;}cout<<ans2<<endl;continue;}ll ans=0;ll t=sqrt(N),l,r;for(ll i=1;i<t-1;i++){ll temp=N/i;ans+=temp+N/temp*(temp-N/(i+1));l=i+1,r=N/(i+1);}for(int i=l;i<=r;i++){ans+=N/i;}//ans+=N/t;cout<<ans<<endl;//<<" "<<ans<<" ";//if(ans2!=ans)cout<<N<<endl;*///}}return 0;
}