题目描述：
给你两个正整数：n 和 target 。
如果数组 nums 满足下述条件，则称其为 美丽数组 。
nums.length == n.nums由两两互不相同的正整数组成。- 在范围
[0, n-1]内，不存在 两个 不同 下标i和j，使得nums[i] + nums[j] == target。
返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 109 + 7。
提示：
1 <= n <= 1091 <= target <= 109
思路：
这题的思路很简单，求小于等于1到target/2的前缀和以及[target,n-target+1]的区间和。很容易想到用等差求和公式（a1+an）*n/2来求解，但是项数太大，求得的结果可能会爆long long ，而且模运算没有除法。这里我们就需要利用逆元：
a/b(mod p)同余于a*b*B(mod p),B是b对于模数p的逆元，且b*B模p同余于1
求逆元主要有两中方式，一种是利用费马小定理，当a,p互质，a对p的逆元B就等于a^p-2(这一步可以用快速幂求).第二种是利用扩展欧几里得，通过b*B(mod p)同余于1，解得B.
最后值得注意的是，如果两数相乘mod p爆long long，我们可以用龟速乘法，原理和快速幂相识，化整体为局部，乘法转化为加法，既然一次性相乘太大，我们可以先加一部分（二进制分割）再模p。
代码：
const int mod=1e9+7; int exgcd(int a,int b,int& x,int& y){ if(!b){ x=1; y=0; return a; } int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } long long km(long long a,long long b){ long long res=1; while(b){ if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res%mod; } int guim(long long a,long long b){ long long res=0; while(b){ if(b&1)res=(res+a)%mod; a=(a+a)%mod; b>>=1; } return res; } class Solution { public: int minimumPossibleSum(int n, int target) { int k=target/2; if(k>=n)k=n; long long ans=(long long)(1+k)*k/2; ans=ans%mod; n=n-k; long long a=target; long long m=km(2,mod-2); cout<<m<<endl; long long r1=(long long)(2*a+n-1)*n%mod; r1=guim(r1,m); ans=(ans+r1)%mod; return ans%mod; } };
