[Acwing] 202. 最幸运的数字 问题转换 + 欧拉函数 + 同余方程

前言

传送门 :

思路

Mycode

ll L ;
ll t=1;
int gcd( ll a, int b) {
    return b ? gcd(b, a % b) : a;
}
ll get_euler(ll c) {
    ll res = c;
    for (int i = 2; i  1) res = res / c * (c - 1);
    return res;
}

ll qmul(ll a, ll b, ll c) {
    ll res = 0;
    while (b) {
        if (b & 1) res = (res + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return res;
}

ll qmi(ll a, ll b, ll c) {
    ll res = 1;
    while (b) {
        if (b & 1) res = qmul(res, a, c);
        a = qmul(a, a, c);
        b >>= 1;
    }
    return res;
}
void solve(){
	int d = gcd(L,8);
	ll c = 9*L/d;
	ll res ;

	ll phi = get_euler(c);
	//必须和10互质
	if(c%2 == 0 || c%5 == 0)res =  0;
	else{
		for(ll i=1;i>t;while(t--)
    while(cin>>L,L)
    solve();
    return 0 ;
}