注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3288]Mato矩阵  

2014-07-22 20:56:46|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description

Mato同学最近正在研究一种矩阵,这种矩阵有n行n列第i行第j列的数为gcd(i,j)。
例如n=5时,矩阵如下:

1 1 1 1 1
1 2 1 2 1
1 1 3 1 1
1 2 1 4 1
1 1 1 1 5

Mato想知道这个矩阵的行列式的值,你能求出来吗?

Input

一个正整数n mod1000000007

Output

n行n列的Mato矩阵的行列式。

Sample Input

5

Sample Output

16

HINT

对于100%的数据,n<=1000000。

Source

By taorunz


Solution

打表找规律裸题。打完表以后发现是φ的前缀积。

不用线性筛的人在这里。巨慢无比。

/**************************************************************
    Problem: 3288
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:852 ms
    Memory:8616 kb
****************************************************************/
 
#include<cstdio>
int i,j,n;long long a[1000010],ans=1,mod=1000000007;
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)a[i]=i;
    for(i=2;i<=n;i++)
    if(a[i]==i)
        for(j=i;j<=n;j+=i)a[j]=a[j]/i*(i-1);
    for(i=1;i<=n;i++)ans=(ans*a[i])%mod;
    printf("%d\n",ans);
}
  评论这张
 
阅读(81)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018