题目大意：给一个N。让你求有多少对A和B，让方程Ax+By=N有自然数解。（N<=100000）
分析：先枚举a再枚举x。对于每个a算出所有可能的b，然后对于b去重。最后便可得到所有的（a，b）对个数。
参考博客：WJBZBMR的空间
/* total 100tests 3522 ms */ #include < iostream > #include < algorithm > #include < vector > using namespace std; const int Max = 100001 ;vector < int > factor[Max]; // A[i]里面按升序存的i的所有约数 typedef vector < int > ::iterator it;typedef vector < int > ::reverse_iterator rit; int enumb[Max * 50 ]; // 对于给定的a，枚举所有的b int n; void cal( int x){ int tmp[ 10000 ]; int cnt = 0 ; for ( int i = 1 ;i * i <= x;i ++ ) if (x % i == 0 ) tmp[cnt ++ ] = i,tmp[cnt ++ ] = x / i; sort(tmp,tmp + cnt); factor[x].push_back(tmp[ 0 ]); for ( int i = 1 ;i < cnt;i ++ ) if (tmp[i] != tmp[i - 1 ]) factor[x].push_back(tmp[i]);} int main(){ // freopen("in.txt","r",stdin); for ( int i = 1 ;i < Max;i ++ ) cal(i); while (cin >> n) { int ans = 0 ; for ( int a = 1 ;a < n;a ++ ) { int * end = enumb; for ( int t = a;t < n;t += a) { int res = n - t; for (rit i = factor[res].rbegin();i != factor[res].rend();i ++ ) { if ( * i > a) * (end ++ ) =* i; else break ; } } if (enumb == end) continue ; sort(enumb,end); ans ++ ; for ( int * i = enumb + 1 ;i != end;i ++ ) if ( * i !=* (i - 1 )) ans ++ ; } cout << ans << endl; } return 0 ;}
转载于:https://www.cnblogs.com/DreamUp/archive/2010/09/01/1814945.html
