這道題，是求n*m的矩形內，有多少對互質的數（x,y）即Gcd( x ,y ) ==1;

這個題首先用到歐拉的質因子分解，再利用容斥定理；

View Code #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #include<cstring> #include<vector> using namespace std; class Node { public:int cnt,num[20]; }node[100024]; void Prime( ) {int prime[10000],cnt=0;bool hash[50024]={0};int t = (int)sqrt( 100000.0 ) + 1;for( int i = 3 ; i <=t ; i+=2 ){if( !hash[i>>1] ){int x = i<<1;for( int j = i * i ; j <=100001; j += x )hash[j>>1] = true; } } prime[cnt++] = 2;for( int i = 1 ;i <= 50000 ; i++ ){if( !hash[i] ){prime[cnt++] = ( i << 1 ) + 1;} }for( int i = 2; i <= 100000 ; i++ ){t = i;node[i].cnt = 0;for( int j = 0 ; j < cnt; j ++ ){if( prime[j] > t ) break;if( t % prime[j] == 0 ){node[i].num[node[i].cnt++] = prime[j];while( t % prime[j] == 0 )t /= prime[j];} }} } long long DFS( int t , int m , int k ) {long long ans = 0;for( int i = t ; i < node[k].cnt ;i ++ ){ans += m/node[k].num[i] - DFS( i + 1 , m/node[k].num[i] , k ); }return ans; } int main( ) {int n ,m,Case;Prime();while( scanf( "%d\n",&Case ) ==1 ){while( Case-- ){long long ans = 0;scanf( "%d %d",&n,&m );for( int i = 1; i <= n ; i++ )ans += m - DFS( 0 , m , i ); printf( "%I64d\n",ans ); } }//system( "pause" );return 0; }

轉載于:https://www.cnblogs.com/bo-tao/archive/2012/07/18/2598128.html

總結

以上是生活随笔為你收集整理的HDU 2841 Visible Trees的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。