首页 > 代码库 > 【BZOJ3518】点组计数 [欧拉函数]
【BZOJ3518】点组计数 [欧拉函数]
点组计数
Time Limit: 20 Sec Memory Limit: 128 MB[Submit][Status][Discuss]
Description
平面上摆放着一个n*m的点阵（下图所示是一个3*4的点阵）。Curimit想知道有多少三点组(a，b，c)满足以a，b，c三点共线。这里a，b，c是不同的3个点，其顺序无关紧要。(即(a，b，c)和
(b，c，a)被认为是相同的）。由于答案很大，故你只需要输出答案对1，000，000，007的余数就可以了。
Input
有且仅有一行，两个用空格隔开的整数n和m。
Output
有且仅有一行，一个整数，表示三点组的数目对1，000，000，007的余数。（1，000。000。007是质数）
Sample Input
3 4
Sample Output
2 0
HINT
对于100%的数据，1< =N．m< =50000
Main idea
给定一个点阵，问有多少组三点共线。
Source
其实我也不知道原式怎么来的，我可能只会推式子啊？QAQ
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 50005;12 const int MOD = 1000000007;13 const int Ny6 = 166666668;14 15 int T;16 int n,m;17 bool isp[ONE];18 int prime[ONE],p_num;19 int phi[ONE];20 s64 Ans;21 22 int get() 23 {24 int res=1,Q=1; char c;25 while( (c=getchar())<48 || c>57)26 if(c==‘-‘)Q=-1;27 if(Q) res=c-48; 28 while((c=getchar())>=48 && c<=57) 29 res=res*10+c-48; 30 return res*Q; 31 }32 33 void Getphi(int MaxN)34 {35 phi[1] = 1;36 for(int i=2; i<=MaxN; i++)37 {38 if(!isp[i])39 prime[++p_num] = i, phi[i] = i - 1;40 for(int j=1; j<=p_num, i*prime[j]<=MaxN; j++)41 {42 isp[i * prime[j]] = 1;43 if(i % prime[j] == 0)44 {45 phi[i * prime[j]] = (s64)phi[i] * prime[j] % MOD;46 break;47 }48 phi[i * prime[j]] = (s64)phi[i] * phi[prime[j]] % MOD;49 }50 }51 }52 53 s64 Get(int a,int b,int num) {return (s64)(a+b) * num / 2 %MOD; }54 s64 Sum(int n,int m) {return ((s64)n*(n-1)/2%MOD) * ((s64)m*(m-1)/2%MOD) % MOD;}55 56 int C(int n)57 {58 int res = (s64)n * (n-1) % MOD * (n-2) % MOD;59 return (s64) res * Ny6 % MOD;60 }61 62 int main()63 {64 Getphi(ONE-1);65 n=get(); m=get();66 if(n > m) swap(n,m);67 for(int d=1; d<=n; d++)68 {69 Ans += phi[d] * Get(n-d,n-(n/d)*d,n/d) % MOD *Get(m-d,m-(m/d)*d,m/d) % MOD;70 Ans %= MOD;71 }72 73 Ans = (Ans - Sum(n,m) + MOD) % MOD;74 Ans = Ans*2%MOD + (s64)C(n)*m%MOD + (s64)C(m)*n%MOD;75 Ans %= MOD;76 77 printf("%lld",Ans);78 }
【BZOJ3518】点组计数 [欧拉函数]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。