/**
 * Modular Multiplicative Inverse: given A and m, 
 *   find x = 1/A mod m, that is -
 *     find x such that: (x * A) mod m == 1.
 * 
 * Modular Division: given A, B and m
 *   find z = A/B mod m, that is -
 *     find z such that: (z * B) mod m == A.
 *
 * @see http://e...content-available-to-author-only...a.org/wiki/Modular_multiplicative_inverse#Computation
 *
 * @author Erel Segal   http://t...content-available-to-author-only...s.fm/rentabrain
 * @date 2010-11-07
 */
 
#include <iostream>
#include <assert.h>
using namespace std;
 
/**
 * Euclid's extended algorithm:
 * Given a,b, Find gcd,x,y that solve the equation:
 *  ax + by = gcd(a,b)
 * @see http://e...content-available-to-author-only...a.org/wiki/Modular_multiplicative_inverse#Computation
 */
void xgcd (int a, int b,
	int& gcd, int& x, int& y) {
	x=0, y=1; 
	int u=1, v=0, m, n, q, r;
	gcd = b;
	while (a!=0) {
		q=gcd/a; r=gcd%a;
		m=x-u*q; n=y-v*q;
		gcd=a; a=r; x=u; y=v; u=m; v=n;
	}
}
 
/**
 * Modular multiplicative inverse:
 * Find x such that: x * A mod m == 1
 * @see http://e...content-available-to-author-only...a.org/wiki/Modular_multiplicative_inverse#Computation
 */
int inverse (int A, int m) {
	assert (0 <= A && A < m);
	int gcd, x, y;
	xgcd (A, m, gcd, x, y);  // x A + y m = gcd
	if (gcd==1) {            // x A + y m = 1
		return (x+m) % m;
	} else {
		throw "no inverse";
	}
}
 
/**
 * Modular division:
 * @return z such that: z * B mod m == A.
 * If there is more than one (i.e. when gcd(A,m)>1) - returns the smaller (??)
 */
int divide (int A, int B, int m) {
	assert (0 <= A && A<m);
	assert (0 <= B && B<m);
 
	int gcd, x, y;
	xgcd (B, m, gcd, x, y);  // x B + y m = gcd(B,m)
	if (A%gcd == 0) {        
		int q = A / gcd;       // x q B + y q m = q gcd = A
		return ((x + m)*q) % (m/gcd);   // Return the smallest result possible
	} else {
		throw "no quotient";
	}
}
 
 
 
 
 
 
void assertInverse(int Y, int m, int expected) {
	int a = inverse(Y, m);
	if (a!=expected) {
		cerr << "ERROR: " << 1 << " / " << Y << " [mod " << m << "] == " << expected << " but got " << a << endl;
	} else {
		cout << 1 << " / " << Y << " [mod " << m << "] == " << expected << endl;
	}
}
 
void assertDivide(int X, int Y, int m, int expected) {
	int a = divide(X, Y, m);
	if (a!=expected) {
		cerr << "ERROR: " << X << " / " << Y << " [mod " << m << "] == " << expected << " but got " << a << endl;
	} else {
		cout << X << " / " << Y << " [mod " << m << "] == " << expected << endl;
	}
}
 
void assertCycle (int Y, int m) {
	for (int Z=1, X=Y; Z<m && X!=0; Z+=1, X=(X+Y)%m) {
		assertDivide(X,Y,m,Z);
	}
}
 
void assertCycles(int m) {
	for (int Y=1; Y<m; ++Y) {
		assertCycle(Y, m);
	}
}
 
 
int main() {
	assertInverse(1, 7, 1);
	assertInverse(2, 7, 4);
	assertInverse(3, 7, 5);
	assertInverse(4, 7, 2);
	assertInverse(5, 7, 3);
	assertInverse(6, 7, 6);
 
	assertCycles(6);
	assertCycles(7);
	assertCycles(8);
	assertCycles(9);
	assertCycles(10);
}
 
 

LyoqCiAqIE1vZHVsYXIgTXVsdGlwbGljYXRpdmUgSW52ZXJzZTogZ2l2ZW4gQSBhbmQgbSwgCiAqICAgZmluZCB4ID0gMS9BIG1vZCBtLCB0aGF0IGlzIC0KICogICAgIGZpbmQgeCBzdWNoIHRoYXQ6ICh4ICogQSkgbW9kIG0gPT0gMS4KICogCiAqIE1vZHVsYXIgRGl2aXNpb246IGdpdmVuIEEsIEIgYW5kIG0KICogICBmaW5kIHogPSBBL0IgbW9kIG0sIHRoYXQgaXMgLQogKiAgICAgZmluZCB6IHN1Y2ggdGhhdDogKHogKiBCKSBtb2QgbSA9PSBBLgogKgogKiBAc2VlIGh0dHA6Ly9lLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5hLm9yZy93aWtpL01vZHVsYXJfbXVsdGlwbGljYXRpdmVfaW52ZXJzZSNDb21wdXRhdGlvbgogKgogKiBAYXV0aG9yIEVyZWwgU2VnYWwgICBodHRwOi8vdC4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5mbS9yZW50YWJyYWluCiAqIEBkYXRlIDIwMTAtMTEtMDcKICovCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxhc3NlcnQuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8qKgogKiBFdWNsaWQncyBleHRlbmRlZCBhbGdvcml0aG06CiAqIEdpdmVuIGEsYiwgRmluZCBnY2QseCx5IHRoYXQgc29sdmUgdGhlIGVxdWF0aW9uOgogKiAgYXggKyBieSA9IGdjZChhLGIpCiAqIEBzZWUgaHR0cDovL2UuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEub3JnL3dpa2kvTW9kdWxhcl9tdWx0aXBsaWNhdGl2ZV9pbnZlcnNlI0NvbXB1dGF0aW9uCiAqLwp2b2lkIHhnY2QgKGludCBhLCBpbnQgYiwKCWludCYgZ2NkLCBpbnQmIHgsIGludCYgeSkgewoJeD0wLCB5PTE7IAoJaW50IHU9MSwgdj0wLCBtLCBuLCBxLCByOwoJZ2NkID0gYjsKCXdoaWxlIChhIT0wKSB7CgkJcT1nY2QvYTsgcj1nY2QlYTsKCQltPXgtdSpxOyBuPXktdipxOwoJCWdjZD1hOyBhPXI7IHg9dTsgeT12OyB1PW07IHY9bjsKCX0KfQoKLyoqCiAqIE1vZHVsYXIgbXVsdGlwbGljYXRpdmUgaW52ZXJzZToKICogRmluZCB4IHN1Y2ggdGhhdDogeCAqIEEgbW9kIG0gPT0gMQogKiBAc2VlIGh0dHA6Ly9lLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5hLm9yZy93aWtpL01vZHVsYXJfbXVsdGlwbGljYXRpdmVfaW52ZXJzZSNDb21wdXRhdGlvbgogKi8KaW50IGludmVyc2UgKGludCBBLCBpbnQgbSkgewoJYXNzZXJ0ICgwIDw9IEEgJiYgQSA8IG0pOwoJaW50IGdjZCwgeCwgeTsKCXhnY2QgKEEsIG0sIGdjZCwgeCwgeSk7ICAvLyB4IEEgKyB5IG0gPSBnY2QKCWlmIChnY2Q9PTEpIHsgICAgICAgICAgICAvLyB4IEEgKyB5IG0gPSAxCgkJcmV0dXJuICh4K20pICUgbTsKCX0gZWxzZSB7CgkJdGhyb3cgIm5vIGludmVyc2UiOwoJfQp9CgovKioKICogTW9kdWxhciBkaXZpc2lvbjoKICogQHJldHVybiB6IHN1Y2ggdGhhdDogeiAqIEIgbW9kIG0gPT0gQS4KICogSWYgdGhlcmUgaXMgbW9yZSB0aGFuIG9uZSAoaS5lLiB3aGVuIGdjZChBLG0pPjEpIC0gcmV0dXJucyB0aGUgc21hbGxlciAoPz8pCiAqLwppbnQgZGl2aWRlIChpbnQgQSwgaW50IEIsIGludCBtKSB7Cglhc3NlcnQgKDAgPD0gQSAmJiBBPG0pOwoJYXNzZXJ0ICgwIDw9IEIgJiYgQjxtKTsKCglpbnQgZ2NkLCB4LCB5OwoJeGdjZCAoQiwgbSwgZ2NkLCB4LCB5KTsgIC8vIHggQiArIHkgbSA9IGdjZChCLG0pCglpZiAoQSVnY2QgPT0gMCkgeyAgICAgICAgCgkJaW50IHEgPSBBIC8gZ2NkOyAgICAgICAvLyB4IHEgQiArIHkgcSBtID0gcSBnY2QgPSBBCgkJcmV0dXJuICgoeCArIG0pKnEpICUgKG0vZ2NkKTsgICAvLyBSZXR1cm4gdGhlIHNtYWxsZXN0IHJlc3VsdCBwb3NzaWJsZQoJfSBlbHNlIHsKCQl0aHJvdyAibm8gcXVvdGllbnQiOwoJfQp9CgoKCgoKCnZvaWQgYXNzZXJ0SW52ZXJzZShpbnQgWSwgaW50IG0sIGludCBleHBlY3RlZCkgewoJaW50IGEgPSBpbnZlcnNlKFksIG0pOwoJaWYgKGEhPWV4cGVjdGVkKSB7CgkJY2VyciA8PCAiRVJST1I6ICIgPDwgMSA8PCAiIC8gIiA8PCBZIDw8ICIgW21vZCAiIDw8IG0gPDwgIl0gPT0gIiA8PCBleHBlY3RlZCA8PCAiIGJ1dCBnb3QgIiA8PCBhIDw8IGVuZGw7Cgl9IGVsc2UgewoJCWNvdXQgPDwgMSA8PCAiIC8gIiA8PCBZIDw8ICIgW21vZCAiIDw8IG0gPDwgIl0gPT0gIiA8PCBleHBlY3RlZCA8PCBlbmRsOwoJfQp9Cgp2b2lkIGFzc2VydERpdmlkZShpbnQgWCwgaW50IFksIGludCBtLCBpbnQgZXhwZWN0ZWQpIHsKCWludCBhID0gZGl2aWRlKFgsIFksIG0pOwoJaWYgKGEhPWV4cGVjdGVkKSB7CgkJY2VyciA8PCAiRVJST1I6ICIgPDwgWCA8PCAiIC8gIiA8PCBZIDw8ICIgW21vZCAiIDw8IG0gPDwgIl0gPT0gIiA8PCBleHBlY3RlZCA8PCAiIGJ1dCBnb3QgIiA8PCBhIDw8IGVuZGw7Cgl9IGVsc2UgewoJCWNvdXQgPDwgWCA8PCAiIC8gIiA8PCBZIDw8ICIgW21vZCAiIDw8IG0gPDwgIl0gPT0gIiA8PCBleHBlY3RlZCA8PCBlbmRsOwoJfQp9Cgp2b2lkIGFzc2VydEN5Y2xlIChpbnQgWSwgaW50IG0pIHsKCWZvciAoaW50IFo9MSwgWD1ZOyBaPG0gJiYgWCE9MDsgWis9MSwgWD0oWCtZKSVtKSB7CgkJYXNzZXJ0RGl2aWRlKFgsWSxtLFopOwoJfQp9Cgp2b2lkIGFzc2VydEN5Y2xlcyhpbnQgbSkgewoJZm9yIChpbnQgWT0xOyBZPG07ICsrWSkgewoJCWFzc2VydEN5Y2xlKFksIG0pOwoJfQp9CgoKaW50IG1haW4oKSB7Cglhc3NlcnRJbnZlcnNlKDEsIDcsIDEpOwoJYXNzZXJ0SW52ZXJzZSgyLCA3LCA0KTsKCWFzc2VydEludmVyc2UoMywgNywgNSk7Cglhc3NlcnRJbnZlcnNlKDQsIDcsIDIpOwoJYXNzZXJ0SW52ZXJzZSg1LCA3LCAzKTsKCWFzc2VydEludmVyc2UoNiwgNywgNik7CgoJYXNzZXJ0Q3ljbGVzKDYpOwoJYXNzZXJ0Q3ljbGVzKDcpOwoJYXNzZXJ0Q3ljbGVzKDgpOwoJYXNzZXJ0Q3ljbGVzKDkpOwoJYXNzZXJ0Q3ljbGVzKDEwKTsKfQoK