首页 > 代码库 > BZOJ 3288 Mato矩阵 线性筛
BZOJ 3288 Mato矩阵 线性筛
题目大意:一个M*M的矩阵,(i,j)位置上的值是gcd(i,j),问这个矩阵的行列式的值。
思路:考试的时候考了这个题,有人居然打表发现规律,简直跪啊。。。
其实用高斯消元之后不难发现,要求的就是从1到m的phi的乘积,一个线性筛就解决了。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1000010 #define MO 1000000007 using namespace std; int x; long long phi[MAX]; int prime[MAX],primes; bool notp[MAX]; void Shake() { phi[1] = 1; for(int i = 2; i <= x; ++i) { if(!notp[i]) prime[++primes] = i,phi[i] = i - 1; for(int j = 1; prime[j] * i <= x; ++j) { notp[prime[j] * i] = true; if(i % prime[j] == 0) { phi[prime[j] * i] = phi[i] * prime[j]; break; } phi[prime[j] * i] = phi[i] * (prime[j] - 1); } } } int main() { cin >> x; Shake(); long long ans = 1; for(int i = 1; i <= x; ++i) ans *= phi[i],ans %= MO; cout << ans << endl; return 0; }
BZOJ 3288 Mato矩阵 线性筛
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。