Magic Pairs
Problem's Link
Mean:
已知N、A0、B0，对于给定X、Y，若A0X+B0Y能被N整除，则AX+BY也能被N整除，求所有的A、B.（0<=A、B<N)
analyse:
这道题目就是先把A0和B0和N都除以他们的最大公约数，然后就是枚举A0和B0的0到N-1倍.
最后快排，注意一下有0的情况.
Time complexity: O(N)
view code
/** * ----------------------------------------------------------------- * Copyright (c) 2016 crazyacking.All rights reserved. * ----------------------------------------------------------------- * Author: crazyacking * Date : 2016-01-08-10.51 */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef long long(LL); typedef unsigned long long(ULL); const double eps(1e-8); int main() { pair<int, int> ans[10010]; int n,a0,b0; scanf("%d%d%d",&n,&a0,&b0); int i = a0 %= n; int j = b0 %= n; int num = 0; do { ans[num++] = make_pair(i, j); i = (i+a0)%n; j = (j+b0)%n; } while(i != a0 || j != b0); sort(ans, ans+num); printf("%d\n",num); for(i = 0; i < num; i++) printf("%d %d\n",ans[i].first,ans[i].second); return 0; }
