【Gym - 100923I】Por Costel and the Pairs（思维题）

Por Costel and the Pairs

Descriptions

有T组测试样例

有n个男的，n个女的，第i个人都有为当前一个大小为i的懒惰值，当一男一女懒惰值的乘积<=n他们就就可以一起跳舞，请问有多少种组合可能；

Example

题目链接

https://vjudge.net/problem/Gym-100923I

 

求n/1+n/2+...+n/n，除法都是整除，但是这接这样写会超时

换个思路

第i个男人可以和前n/i个女人跳舞，女的也是这样，会有i个重复，但会多减一个坐标相同的，加上就好

2*(n/i-i)+1要不小于0，因为人数不可能为负数

即n/i-i>=0  解得i*i<=n

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 1000010

using namespace std;

ll T,n;

int main()

{

    freopen("perechi3.in","r",stdin);

    freopen("perechi3.out","w",stdout);

    cin>>T;

    while(T--)

    {

        cin>>n;

        ll ans=;

        for(int i=;i*i<=n;i++)

        {

            ans+=*(n/i-i)+;

        }

        cout<<ans<<endl;

    }

    return ;

}