这道题进去看status发现代码好短,肯定有什么规律,就把后面那部分打个表一看发现就是n*m然后就交了一发Wa了……以为结论是错的后来去找题解发现是对的,就是有个地方忘记mod了
至于证明吗看PoPoQQQ大神的题解吧: http://blog.csdn.net/PoPoQQQ/article/details/46820313
//coder : davidwang #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <vector> #include <queue> #include <set> #include <map> #include <bitset> #include <deque> #include <iostream> using namespace std; #define LL long long #define X first #define Y second template<typename T> inline T sqr(const T &x){ return x*x; } inline int read() { int ret=0,f=1; char ch; for (ch=getchar();ch<'0' || ch>'9';ch=getchar()) if (ch=='-') f=-f; for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-'0'; return ret*f; }; const int mod = 998244353; inline LL phi(LL x){ LL i,ret=x; for (i=2;i*i<=x;i++){ if (x%i==0){ ret=ret/i*(i-1); while (x%i==0) x/=i; } } if (x!=1) ret=ret/x*(x-1); return ret; } int main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif LL n,m; cin>>n>>m; LL a=phi(n)%mod,b=phi(m)%mod; n%=mod; m%=mod; a=a*b%mod; a=a*n%mod; a=a*m%mod; cout<<a<<endl; return 0; }