E

题目意思：n之前有多少对是满足的。

打表找规律，可以发现一定是一组答案，
令,式子就变成了,倍，可以证得。

原式子

移项
把看成常数的话，那么两个解由韦达定理就有：

,即;这个就是递推关系式
如果是第一组答案的话，那么下一组答案就为;

第一组答案，
由递推式，下面依次是：,,,

枚举x，直到答案超过了1e18,停止。只保留更大的那个答案，然后，二分查询。

代码：

#include<bits/stdc++.h>
using namespace std;
#define bug(x) cerr<<#x<<" : "<<x<<endl;
const int N=5e6+20;
const int mod=1e9+7;
const int INF=2e9;
typedef long long ll;

ll n;
ll ans[N],tt=0;


int main() {
    for(ll i=2;i<=1000000;i++){//y2=i*i*x-y1,递推式
        ll x=i,y=i*i*i;
        ans[++tt]=y;
        while(1){
            if(y>=(1e18+x)/i/i) break;//要用除法判断，不然容易爆long long.
            x=i*i*y-x;
            swap(x,y);
            ans[++tt]=y;
        }
    }
    sort(ans+1,ans+1+tt);
    int T;
    cin>>T;
    while(T--){
        ll n;
        cin>>n;
        cout<<upper_bound(ans+1,ans+1+tt,n)-ans<<endl;
    }
}

J

题意：给你n个点的无向完全图，每条边要么是黑色，要么是白色，问能练成几个三角形，三角形的三条边的颜色是相同的。

思路：从n个点中选三个构成三角形，总的数量是个，那相同颜色的该如何解决，我们可以从反面来想不符合三条边同色的三角形，

如图我们可以发现，不同色，三条边一定有一条边的颜色是不同于其他两条边的，即有两个异色角，所以问题变成统计多少个异色角，每条边被使用了两次，除以2，就是不符合的数量，我们可以统计每一个点出来的边，黑白两种颜色各有多少种，如果是,一黑二白或者二黑一白就存在异色角。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
vector<int>G[maxn];
set<ll>st;
int vis[maxn],link[maxn],out[maxn];

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b,u;
    unsigned get()
    {
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    bool read() {
      while (!u) u = get();
      bool res = u & 1;
      u >>= 1; return res;
    }
    void srand(int x)
    {
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
          u = 0;
    }
}

using namespace GenHelper;
bool edge[8005][8005];



int main(){
 int n, seed;
  cin >> n >> seed;
  srand(seed);
  for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            edge[j][i] = edge[i][j] = read();
    ll ans=1ll*n*(n-1)*(n-2)/6,res=0;
    for(int i=0;i<n;i++){
        int c1=0,c2=0;
        for(int j=0;j<n;j++){
            if(i!=j){
                if(edge[i][j]){
                    c1++;
                }
                else c2++;
            }
        }
        res+=c1*c2;
    }
    cout<<ans-res/2<<endl;
     return 0;
}