人是傻啊。。

NTT……然而我并不会写
无限Orz会NTT的@Asm.Def 神犇

用 map 很容易
http://paste.ubuntu.com/11130311/

论一个人可以脑抽到什么境界。。

友情附送用来找规律的暴力程序

题面坑爹，行列编号是从0开始的

然而LCA并没有什么卵用……
常数巨大……
代码这么长我是不是应该直接写LCT了……

回文自动机来一发
看错数据调好久，弃疗交上去发现A了，惊呼数据没过AC了（看错标准输出了囧）。。~~~~(>_<)~~~~

假如强制在线该怎么做……

强行不用矩阵→_→初等方法默默飘过

咦？为啥没人打表。。

卧槽我不是故意刷榜的。。我就是想事实HASHSIZE和时间的关系。。

回复 @cstdio :
囧。。事实证明1007就更快了，7的话貌似也特别快。。这是取余时候的常数太大了吗。。

回复 @cstdio :
为啥HASH_SIZE开小点会比开大了更快。。而且开的足够大以后直接TLE了，这是什么鬼。。1000007的话TLE,100007跑到第三，10007就rank1了。。

弱弱的50分暴力。。
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int ans,n;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int main()
{
cin>>n;
for (int i=1;i<=sqrt(n);i++)
for (int j=1;j<=i-1;j++)
{
if (gcd(i,j)==1) ans+=n/(i*(i+j));
}
cout<<ans;
}

回复 @rpCardinal :
这个数据好坑

回复 @Roudnis :

OMG!!!哈希大法好可怕啊……前面我说的那个二分查找结构只要改成一个哈希链表结构就可以随便做啦！复杂度直接去掉一个log，变成了$T(N) = \sum_{i=1}^{\sqrt{N}} (\sqrt{\frac{N}{i}} + \sqrt{i} ) × \frac{N}{P}$

O（nlogn）【快排】的算法被卡成这样，常数大不是我的错。。。