感觉自己做法好sb QAQ
完全看不懂楼上神犇做法Orz

好慢，感觉像是降了一级复杂度Orz常数帝，绳命中第一道树形DP

选对模数很重要不要选233333 QAQ

人是傻啊。。

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;
}