[bzoj4816][sdoi2017]数字表格

关键词：

3
2 3
4 5
6 7

1
6
960

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 1000010
#define maxt 2828
#define MOD 1000000007
#define LL long long

void gcd(LL a, LL b, LL& x, LL& y) {
	if(!b){ x = 1; y = 0; return ; }
	gcd(b, a % b, y, x); y -= a / b * x;
	return ;
}
int inv(LL a) {
	LL x, y;
	gcd(a, MOD, x, y);
	return (x % MOD + MOD) % MOD;
}

int prime[maxn], cp, mu[maxn], smu[maxn], f[maxn], tf[maxn], invt[maxn];
bool vis[maxn];
void init() {
	mu[1] = 1; smu[1] = 1;
	for(int i = 2; i < maxn; i++) {
		if(!vis[i]) prime[++cp] = i, mu[i] = -1;
		for(int j = 1; i * prime[j] < maxn && j <= cp; j++) {
			vis[i*prime[j]] = 1;
			if(i % prime[j] == 0){ mu[i*prime[j]] = 0; break; }
			mu[i*prime[j]] = -mu[i];
		}
		smu[i] = smu[i-1] + mu[i];
	}
	int f1 = 0, f2 = 1; tf[1] = invt[1] = 1; invt[0] = 1;
	for(int i = 2; i < maxn; i++) {
		swap(f1, f2); f2 += f1; if(f2 >= MOD) f2 -= MOD;
		tf[i] = (LL)tf[i-1] * f2 % MOD;
		invt[i] = inv(tf[i]);
	}
	return ;
}

LL get[maxt][maxt];
LL g(int n, int m) {
	if(n < maxt && m < maxt) {
		LL& ans = get[n][m];
		if(ans) return ans;
		for(int i = 1, lst; i <= n; i = lst + 1) {
			lst = min(n / (n / i), m / (m / i));
			ans += (LL)(n / i) * (m / i) * (smu[lst] - smu[i-1]);
		}
		return ans;
	}
	LL ans = 0;
	for(int i = 1, lst; i <= n; i = lst + 1) {
		lst = min(n / (n / i), m / (m / i));
		ans += (LL)(n / i) * (m / i) * (smu[lst] - smu[i-1]);
	}
	return ans;
}

int Pow(int a, LL b) {
	int t = a, ans = 1;
	while(b) {
		if(b & 1) ans = (LL)ans * t % MOD;
		t = (LL)t * t % MOD; b >>= 1;
	}
	return ans;
}

int main() {
	init();
	
	int T = read();
	while(T--) {
		int n = read(), m = read(), ans = 1;
		if(n > m) swap(n, m);
		for(int i = 1, lst; i <= n; i = lst + 1) {
			lst = min(n / (n / i), m / (m / i));
			ans = (LL)ans * Pow((LL)tf[lst] * invt[i-1] % MOD, g(n / i, m / i)) % MOD;
		}
		printf("%d\n", ans);
	}
	
	return 0;
}

bzoj4816[sdoi2017]数字表格(代码片段)

题面https://www.lydsy.com/JudgeOnline/problem.php?id=4816题解显然是莫比乌斯反演首先得出然后发现我们要把d提出去这样就好做了跟SDOI2015的一道题类似因为$leftlfloorfracnpightfloorleftlfloorfracmpightfloor$只有$(sqrtn+sqrtm)$种取 查看详情

[bzoj4816][sdoi2017]数字表格

[BZOJ4816][Sdoi2017]数字表格试题描述Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,j的最... 查看详情

bzoj4816:[sdoi2017]数字表格

问题：　　[n/k]/d==[n/(kd)];　　线性筛正确性证明　　这么求逆元Right？a=k*p;　　1LL转化作用域　　longlong做数组下标#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;typedeflonglongLint;constintmaxn=100 查看详情

bzoj4816:[sdoi2017]数字表格

DescriptionDoris刚刚学习了\(fibonacci\)数列。用\(f[i]\)表示数列的第\(i\)项，那么\[\beginalignf[0]&=0\\f[1]&=1\\f[n]&=f[n-1]+f[n-2],n>=2\endalign\]Doris用老师的超级计算机生成了一个\(n\timesm\)的表格，第\(i\)行第\(j\)列的格子中的 查看详情

[bzoj4816][sdoi2017]数字表格(莫比乌斯反演)(代码片段)

4816:[Sdoi2017]数字表格TimeLimit:50Sec  MemoryLimit:128MBSubmit:1259  Solved:625[Submit][Status][Discuss]DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2] 查看详情

bzoj4816[sdoi2017]数字表格

TimeLimit: 50Sec  MemoryLimit: 128MBSubmit: 646  Solved: 296DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算 查看详情

bzoj4816[sdoi2017]数字表格莫比乌斯反演

【BZOJ4816】[Sdoi2017]数字表格DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,... 查看详情

bzoj4816:[sdoi2017]数字表格

题面戳我Sol摆公式：(ans=Pi_{i=1}^{n}Pi_{j=1}^{m}f[gcd(i,j)])考虑每个gcd的贡献，设n<m则就是(Pi_{d=1}^{n}Pi_{i=1}^{lfloorfrac{n}{d} floor}Pi_{j=1}^{lfloorfrac{m}{d} floor}f[d]*[gcd(i,j)==1])(=Pi_{d=1}^{ 查看详情

bzoj4816[sdoi2017]数字表格

题目链接以下除法均指下取整[prod_{i=1}^nprod_{j=1}^mf(gcd(i,j))=prod_{x}f(x)^{sum_isum_j[gcd(i,j)=x]}=prod_{x}f(x)^{sum_{x|d}mu(frac{d}{x})frac{n}{d}frac{m}{d}}=prod_{d}(prod_{x|d}f(x)^{mu(frac{d 查看详情

bzoj.4816.[sdoi2017]数字表格(莫比乌斯反演)(代码片段)

题目链接总感觉博客园的\(Markdown\)很。。\(gouzhi\)，可以看这的。这个好像简单些啊，只要不犯sb错误\(Description\)　　用\(f[i]\)表示\(Fibonacci\)数列的第\(i\)项，求\[\prod_i=1^n\prod_j=1^mf[\gcd(i,j)]\mod(10^9+7)\]\(Solution\)\[\beginalignedAns& 查看详情

bzoj4816sdoi2017数字表格(代码片段)

一开始只推出O(TN)的做法，后来看了看发现再推一步就好了。我们只需要枚举gcd就可以啦。然后我们改变一下枚举顺序 设T为dk预处理中间那部分前缀积就好了。1#include<bits/stdc++.h>2usingnamespacestd;3constintN=1e6+10,mod=1e9+7;4intn,m,... 查看详情

sdoi2017round1day1题解（bzoj4816bzoj4817bzoj4818）

不知道有几个AK的，除了出题人SB搬了个BZOJ3779以外，应该没什么因素阻碍AK吧。要是SCOI考这套题多好。BZOJ4816数字表格SB反演，推出$ans=prod_{i=1}^nf^{sum_{j=1}^{leftlfloorfracni ight floor}mu(j)leftlfloorfracn{ij} ight floorleftlfloorfrac 查看详情

bzoj4816数字表格

...函数，话说上次考莫比鸟斯就是去年吧，好像题目名也叫数字表格，只不过多了一个前缀"Crash的"。慢慢推吧， 查看详情

[sdoi2017]数字表格

[Sdoi2017]数字表格http://www.lydsy.com/JudgeOnline/problem.php?id=4816TimeLimit: 50Sec  MemoryLimit: 128MBDescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2 查看详情

bzoj4816数字表格（莫比乌斯反演）

【BZOJ4816】数字表格（莫比乌斯反演）题面BZOJ求[prod_{i=1}^nprod_{j=1}^mf[gcd(i,j)]]题解忽然不知道这个要怎么表示。。。就写成这样吧。。[prod_{d=1}^nprod_{i=1}^nprod_{j=1}^mif(gcd(i,j)==d)f[gcd(i,j)]]直接把(f[d])提出来[prod_{d=1}^{n}f[d]^ 查看详情

[bzoj4816]数字表格莫比乌斯反演

第一次见到这种形式，推了两步就被卡住了。没想到还能这么迁移QAQ，真强！题目设$f(i)$为第$i$项斐波那契数列要求计算$$ans=prod_{i=1}^nprod_{j=1}^mf(gcd(i,j))$$枚举$d=gcd$得到$$ans=prod_{d=1}^nf(d)^{sum_{i=1}^nsum_{j=1}^m[gcd(i,j)==d]}$$然后反演得... 查看详情

p3704[sdoi2017]数字表格

#include<iostream>#include<cstdio>#include<cstring>#defineLLlonglong#definemaxn1000009#defineNmaxn+10#defineM1000000007usingnamespacestd;intn,m;intq;LLksm(LLa,LLp){ LLans=1; for(;p;p 查看详情

学术篇sdoi2017数字表格

======传======送======门======在======里======面======去年忘记可以预处理了...然后就打了10pts的暴力...现在学了莫比乌斯反演就可以来做了=======================================这个题目看着非常的简单,就是要求这个式子[prod_{i=1}^Nprod_{j=1}^Mf[gcd... 查看详情